# What is an asymptotically tight upper bound?

From what I have learned asymptotically tight bound means that it is bound from above and below as in theta notation. But what does asymptotically tight upper bound mean for Big-O notation?

• This confused me too. Why can't authors say "theta"? Why invent unnecessary terms? – beroal May 4 '17 at 9:01

Saying that a big-O bound is "asymptotically tight" basically means that the author should have written $\Theta(-)$. For example, $O(x^2)$ means that it's no more than some constant times $x^2$ for all large enough $x$; "asymptotically tight" means it really is some constant times $x^2$ for large enough $x$ and not, say, some constant times $x^{1.999}$.
Suppose you have an algorithm that is given as input an array of integers $A$. The algorithm scans through the array, and increments a counter initially set to zero everytime it sees an element that is an even integer. We can prove the algorithm runs in say $O(n^3)$ time, where $n$ is the number of elements in $A$. But we can also give a tighter bound, and say it runs in time $O(n)$. This bound is asymptotically tight: in fact, since reading the input already takes $\Omega(n)$ time, we could be more precise and say the algorithm takes $\Theta(n)$ time.
• +1, but I think a danger in your choice of example is that it can be misinterpreted to be claiming that for an upper bound to be asymptotically tight, it must be that no faster algorithm for this problem is possible, when that's not true. (I say this because whenever I see the "You need at least $\Omega(n)$ time to read the input" observation, it's being used to justify such a "no faster algorithm can exist" claim.) – j_random_hacker Dec 22 '16 at 22:04
$$\Theta$$ means we have both a lower bound and an upper bound. For example if $$f(n) = \Theta(n^2)$$ then $$c_1 n^2 <= f(n) <= c_2 n^2$$ for large n.
However, we have functions that are not always close to the upper bound. For example, $$\sin n \cdot n^2 = O(n^2)$$, but it is not $$\Theta (n^2)$$. Still, we cannot reduce the $$n^2$$. $$\sin n \cdot n^2 ≠ o(n^2)$$. That makes $$n^2$$ an asymptotic tight upper bound.