Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Tight Big Oh Bounds

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 function f(n)=O(g(n)). If for every function h(n) such that f(n)=O(h(n)) it is also true that g(n)=O(h(n)), then we say that g(n) is a tight asymptotic bound  on f(n).

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

By Definition gif, 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)=8n+128. Then there exists a function h(n) such that f(n)=8n+128=O(h(n)), but for which tex2html_wrap_inline58891. Since 8n+128=O(h(n)), by the definition of big oh there exist positive constants c and tex2html_wrap_inline58265 such that tex2html_wrap_inline58899 for all tex2html_wrap_inline58299.

Clearly, for all tex2html_wrap_inline58277, tex2html_wrap_inline58905. Therefore, tex2html_wrap_inline58907. 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.

next up previous contents index

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