Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline57984 used to show a big oh relation.

Fallacy  Consider non-negative functions f(n), tex2html_wrap_inline58638, and tex2html_wrap_inline58184, such that tex2html_wrap_inline58642. Since tex2html_wrap_inline58644 for all integers tex2html_wrap_inline57996 if tex2html_wrap_inline58648, then by Definition gif tex2html_wrap_inline58650.

This fallacy often results from the following line of reasoning: Consider the function tex2html_wrap_inline58652. Let tex2html_wrap_inline58654 and tex2html_wrap_inline58482. Then f(n) must be O(n), since tex2html_wrap_inline58662 for all tex2html_wrap_inline58018. 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_inline58174, tex2html_wrap_inline58176, tex2html_wrap_inline58638, and tex2html_wrap_inline58184, such that tex2html_wrap_inline58170, tex2html_wrap_inline58172, and for all integers tex2html_wrap_inline57996, tex2html_wrap_inline58684, then tex2html_wrap_inline58686.

This fallacy arises from the following line of reasoning. Consider the function tex2html_wrap_inline58688 and tex2html_wrap_inline58690. Since tex2html_wrap_inline58692 for all values of tex2html_wrap_inline58476, we might be tempted to conclude that tex2html_wrap_inline58696. In fact, such a conclusion is erroneous. For example, consider tex2html_wrap_inline58118 and tex2html_wrap_inline58700. Clearly, the former is tex2html_wrap_inline58122 and the latter is tex2html_wrap_inline58434. Clearly too, tex2html_wrap_inline58706 for all values of tex2html_wrap_inline57996!

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_inline58714 and tex2html_wrap_inline58716, respectively. Fallacy gif demonstrates that it is an error to conclude from the fact that tex2html_wrap_inline58718 for all tex2html_wrap_inline57996 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_inline57984, that algorithm A is faster than algorithm B? The next fallacy addresses this issue.

Fallacy  Given non-negative functions tex2html_wrap_inline58174, tex2html_wrap_inline58176, tex2html_wrap_inline58638, and tex2html_wrap_inline58184, such that tex2html_wrap_inline58170, tex2html_wrap_inline58172, and for all integers tex2html_wrap_inline57996, tex2html_wrap_inline58684, there exists an integer tex2html_wrap_inline57984 for which then tex2html_wrap_inline58750.

This fallacy arises from a similar line of reasoning as the preceding one. Consider the function tex2html_wrap_inline58688 and tex2html_wrap_inline58690. Since tex2html_wrap_inline58692 for all values of tex2html_wrap_inline58476, we might be tempted to conclude that there exists a value tex2html_wrap_inline57984 for which tex2html_wrap_inline58762. Such a conclusion is erroneous. For example, consider tex2html_wrap_inline58764 and tex2html_wrap_inline58766. Clearly, the former is tex2html_wrap_inline58122 and the latter is tex2html_wrap_inline58434. Clearly too, since tex2html_wrap_inline58706 for all values of tex2html_wrap_inline57996, there does not exist any value tex2html_wrap_inline58776 for which tex2html_wrap_inline58762.

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_inline57116 is like tex2html_wrap_inline58790 and can be used to compare any two functions. However, not all functions are commensurate.gif Consider the following functions:

eqnarray1701

Clearly, there does not exist a constant c for which tex2html_wrap_inline58020 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_inline58812 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.