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

More Big Oh Fallacies and Pitfalls

The purpose of this section is to dispel some common misconceptions about big oh. The next fallacy is related to the selection of the constants c and tex2html_wrap_inline59043 used to show a big oh relation.

Fallacy  Consider non-negative functions f(n), tex2html_wrap_inline59693, and tex2html_wrap_inline59241, such that tex2html_wrap_inline59697. Since tex2html_wrap_inline59699 for all integers tex2html_wrap_inline59063 if tex2html_wrap_inline59703, then by Definition gif tex2html_wrap_inline59705.

This fallacy often results from the following line of reasoning: Consider the function tex2html_wrap_inline59707. Let tex2html_wrap_inline59709 and tex2html_wrap_inline59539. Then f(n) must be O(n), since tex2html_wrap_inline59717. However, this line of reasoning is false because according to Definition gif, c must be a positive constant, not a function of n.

The next fallacy involves a misunderstanding of the notion of the asymptotic upper bound.

Fallacy  Given non-negative functions tex2html_wrap_inline59231, tex2html_wrap_inline59233, tex2html_wrap_inline59693, and tex2html_wrap_inline59241, such that tex2html_wrap_inline59227, tex2html_wrap_inline59229, and for all integers tex2html_wrap_inline59063, tex2html_wrap_inline59737, then tex2html_wrap_inline59739.

This fallacy arises from the following line of reasoning. Consider the function tex2html_wrap_inline59741 and tex2html_wrap_inline59743. Since tex2html_wrap_inline59745 for all values of tex2html_wrap_inline59533, we might be tempted to conclude that tex2html_wrap_inline59749. In fact, such a conclusion is erroneous. E.g., consider tex2html_wrap_inline59175 and tex2html_wrap_inline59753. Clearly, the former is tex2html_wrap_inline59179 and the latter is tex2html_wrap_inline59491. Clearly too, tex2html_wrap_inline59759 for all values of tex2html_wrap_inline59063!

The previous fallacy essentially demonstrates that while we may know how the asymptotic upper bounds on two functions are related, we don't necessarily know, in general, the relative behavior of the two bounded functions.

This fallacy often arises in the comparison of the performance of algorithms. Suppose we are comparing two algorithms, A and B, to solve a given problem and we have determined that the running times of these algorithms are tex2html_wrap_inline59767 and tex2html_wrap_inline59769, respectively. Fallacy gif demonstrates that it is an error to conclude from the fact that tex2html_wrap_inline59771 that algorithm A will solve the problem faster than algorithm B for all problem sizes.

But what about any one specific problem size? Can we conclude that for a given problem size, say tex2html_wrap_inline59043, that algorithm A is faster than algorithm B? The next fallacy addresses this issue.

Fallacy  Given non-negative functions tex2html_wrap_inline59231, tex2html_wrap_inline59233, tex2html_wrap_inline59693, and tex2html_wrap_inline59241, such that tex2html_wrap_inline59227, tex2html_wrap_inline59229, and for all integers tex2html_wrap_inline59063, tex2html_wrap_inline59737, there exists an integer tex2html_wrap_inline59043 for which then tex2html_wrap_inline59801.

This fallacy arises from a similar line of reasoning as the preceding one. Consider the function tex2html_wrap_inline59741 and tex2html_wrap_inline59743. Since tex2html_wrap_inline59745 for all values of tex2html_wrap_inline59533, we might be tempted to conclude that there exists a value tex2html_wrap_inline59043 for which tex2html_wrap_inline59813. Such a conclusion is erroneous. E.g., consider tex2html_wrap_inline59815 and tex2html_wrap_inline59817. Clearly, the former is tex2html_wrap_inline59179 and the latter is tex2html_wrap_inline59491. Clearly too, since tex2html_wrap_inline59759 for all values of tex2html_wrap_inline59063, there does not exist any value tex2html_wrap_inline59827 for which tex2html_wrap_inline59813.

The final fallacy shows that not all functions are commensurate :

Fallacy  Given two non-negative functions f(n) and g(n) then either f(n)=O(g(n)) or g(n)=O(f(n)).

This fallacy arises from thinking that the relation tex2html_wrap_inline58163 is like tex2html_wrap_inline59841 and can be used to compare any two functions. However, not all functions are commensurate.gif Consider the following functions:

eqnarray1618

Clearly, there does not exist a constant c for which tex2html_wrap_inline59077 for any even integer n, since the g(n) is zero and f(n) is not. Conversely, there does not exist a constant c for which tex2html_wrap_inline59863 for any odd integer n, since the f(n) is zero and g(n) is not. Hence, neither f(n)=O(g(n)) nor g(n)=O(f(n)) is true.


next up previous contents index

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