Upper Bounds and Tight Upper Bounds

  • Topic:
  • Thread starter Sudharaka
  • Start date
  • Tags Tags
    Bounds
2 replies · 2K views · last reply
Sudharaka
Gold Member
MHB
Messages
1,558
Reaction score
1
Hi everyone, :)

What is a Tight Upper Bound? Is it the least upper bound? But then tight upper bound will be equivalent to the supremum. :confused:
 
Sudharaka said:
Hi everyone, :)

What is a Tight Upper Bound? Is it the least upper bound? But then tight upper bound will be equivalent to the supremum. :confused:

Hi! :)

I think you are talking about the $\Theta$ bound.

It's a different type of bound.

Suppose we have the function $f(n) = n^3 + 2n^2$.
Its tight upper bound is $\Theta(n^3)$.
This is not a supremum (or least upper bound), since the function doesn't have one - it goes up to infinity.
The point it that it goes up asymptotically with $n^3$.

For instance $O(n^4)$ is an asymptotic upper bound, while $\Omega(n)$ is an asymptotic lower bound.
A tight bound is one that is both.
 
I like Serena said:
Hi! :)

I think you are talking about the $\Theta$ bound.

It's a different type of bound.

Suppose we have the function $f(n) = n^3 + 2n^2$.
Its tight upper bound is $\Theta(n^3)$.
This is not a supremum (or least upper bound), since the function doesn't have one - it goes up to infinity.
The point it that it goes up asymptotically with $n^3$.

For instance $O(n^4)$ is an asymptotic upper bound, while $\Omega(n)$ is an asymptotic lower bound.
A tight bound is one that is both.

Thanks much. That makes perfect sense now. :)