HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

What is an asymptotically tight upper bound?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
tightboundwhatasymptoticallyupper

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#19141, answer score: 23

Revisions (0)

No revisions yet.