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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ This confused me too. Why can't authors say "theta"? Why invent unnecessary terms? $\endgroup$– beroalCommented May 4, 2017 at 9:01
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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}$.
answered Dec 20, 2013 at 7:56
-
$\begingroup$ $\Theta$ would imply $\Omega$, which is not necessarily true. $\endgroup$– apenCommented Sep 21, 2022 at 18:12
$\begingroup$
$\endgroup$
2
Here's an example explaining it (and a concrete example for David's fine answer).
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.
-
3$\begingroup$ +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.) $\endgroup$ Commented Dec 22, 2016 at 22:04
-
1$\begingroup$ @j_random_hacker You are right, we should be careful with that. To reiterate, ofcourse an asymptotically tight bound says nothing about the possibility of having a faster algorithm in general. $\endgroup$– JuhoCommented Dec 23, 2016 at 0:47
$\begingroup$
$\endgroup$
$\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.
