Question Detail: 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?
Asked By : nangal.vivek
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19141
Answered By : David Richerby
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}$.
