Logo 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_inline59165 and tex2html_wrap_inline59167, then tex2html_wrap_inline59169.

Consider the equations:

eqnarray1375

Clearly, it is reasonable to conclude that tex2html_wrap_inline59169.

However, consider these equations:

eqnarray1377

It does not follow that tex2html_wrap_inline59169. E.g., tex2html_wrap_inline59175 and tex2html_wrap_inline59177 are both tex2html_wrap_inline59179, but they are not equal.

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

Consider functions f, g, and h, such that f(n)=h(g(n)). It is reasonable to conclude that tex2html_wrap_inline59193 provided that tex2html_wrap_inline59195 is an invertible function. However, while we may write f(n)=O(h(n)), the equation tex2html_wrap_inline59183 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_inline59085 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_inline58163, does not really mean that O is a mathematical function!


next up previous contents index

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