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

Big Oh Fallacies and Pitfalls

Unfortunately, the way we write big oh notation can be misleading to the naıve reader. This section presents two fallacies which arise because of a misinterpretation of the notation.

Fallacy  Given that tex2html_wrap_inline58389 and tex2html_wrap_inline58391, then tex2html_wrap_inline58393.

Consider the equations:

eqnarray1452

Clearly, it is reasonable to conclude that tex2html_wrap_inline58393.

However, consider these equations:

eqnarray1454

It does not follow that tex2html_wrap_inline58393. For example, tex2html_wrap_inline58399 and tex2html_wrap_inline58401 are both tex2html_wrap_inline58403, but they are not equal.

Fallacy  If f(n)=O(g(n)), then tex2html_wrap_inline58407.

Consider functions f, g, and h, such that f(n)=h(g(n)). It is reasonable to conclude that tex2html_wrap_inline58417 provided that tex2html_wrap_inline58419 is an invertible function. However, while we may write f(n)=O(h(n)), the equation tex2html_wrap_inline58407 is nonsensical and meaningless. Big oh is not a mathematical function, so it has no inverse!

The reason for these difficulties is that we should read the notation tex2html_wrap_inline58309 as ``f(n) is big oh n squared'' not ``f(n) equals big oh of n squared.'' The equal sign in the expression does not really denote mathematical equality! And the use of the functional form, tex2html_wrap_inline57397, does not really mean that O is a mathematical function!

next up previous contents index

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