MHB Upper Bounds and Tight Upper Bounds

  • Thread starter Thread starter Sudharaka
  • Start date Start date
  • Tags Tags
    Bounds
AI Thread Summary
A tight upper bound, often represented as Θ, refers to a function that asymptotically matches the growth rate of another function, such as f(n) = n^3 + 2n^2, which has a tight upper bound of Θ(n^3). This is distinct from the supremum or least upper bound, as the function can increase indefinitely. In contrast, O(n^4) serves as an asymptotic upper bound, while Ω(n) represents an asymptotic lower bound. A tight bound effectively captures both upper and lower asymptotic behaviors. Understanding these distinctions clarifies the concept of tight upper bounds in mathematical analysis.
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:
 
Mathematics news on Phys.org
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. :)
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top