What is an asymptotically tight upper bound?

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