Upper Bounds and Tight Upper Bounds

[Sudharaka]

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.

 

[I like Serena]

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.

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.

 

[Sudharaka]

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. :)