15
$\begingroup$

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?

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

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}$.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • 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$ – j_random_hacker Dec 22 '16 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$ – Juho Dec 23 '16 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.