Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

Big oh notation characterizes the asymptotic behavior of a function
by providing an upper bound on the rate at which the function grows
as *n* gets large.
Unfortunately, the notation does not tell us how close
the actual behavior of the function is to the bound.
That is, the bound might be very close (tight)
or it might be overly conservative (loose).

The following definition tells us what makes a bound tight, and how we can test to see whether a given asymptotic bound is the best one available.

Definition (Tightness)Consider a functionf(n)=O(g(n)). If for every functionh(n) such thatf(n)=O(h(n)) it is also true thatg(n)=O(h(n)), then we say thatg(n) is atight asymptotic boundonf(n).

For example, consider the function *f*(*n*)=8*n*+128.
In Section ,
it was shown that .
However, since *f*(*n*) is a polynomial in *n*,
Theorem tells us that *f*(*n*)=*O*(*n*).
Clearly *O*(*n*) is a tighter bound on the asymptotic behavior of *f*(*n*)
than is .

By Definition ,
in order to show that *g*(*n*)=*n* is a tight bound on *f*(*n*),
we need to show that for every function *h*(*n*)
such that *f*(*n*)=*O*(*h*(*n*)), it is also true that *g*(*n*)=*O*(*h*(*n*)).

We will show this result using proof by contradiction:
Assume that *g*(*n*) is *not* a tight bound for *f*(*n*)=8*n*+128.
Then there exists a function *h*(*n*)
such that *f*(*n*)=8*n*+128=*O*(*h*(*n*)),
but for which .
Since 8*n*+128=*O*(*h*(*n*)), by the definition of big oh there exist
positive constants *c* and such that
for all .

Clearly, for all , .
Therefore, .
But then, by the definition of big oh,
we have the *g*(*n*)=*O*(*h*(*n*))--a contradiction!
Therefore, the bound *f*(*n*)=*O*(*n*) is a tight bound.

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.