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

Asymptotic Notation


Suppose we are considering two algorithms, A and B, for solving a given problem. Furthermore, let us say that we have done a careful analysis of the running times of each of the algorithms and determined them to be tex2html_wrap_inline59029 and tex2html_wrap_inline59031, respectively, where n is a measure of the problem size. Then it should be a fairly simple matter to compare the two functions tex2html_wrap_inline59029 and tex2html_wrap_inline59031 to determine which algorithm is the best!

But is it really that simple? What exactly does it mean for one function, say tex2html_wrap_inline59029, to be better than another function, tex2html_wrap_inline59031? One possibility arises if we know the problem size a priori. E.g., suppose the problem size is tex2html_wrap_inline59043 and tex2html_wrap_inline59045. Then clearly algorithm A is better than algorithm B for problem size tex2html_wrap_inline59043.

In the general case, we have no a priori knowledge of the problem size. However, if it can be shown, say, that tex2html_wrap_inline59053, then algorithm A is better than algorithm B regardless of the problem size.

Unfortunately, we usually don't know the problem size beforehand, nor is it true that one of the functions is less than or equal the other over the entire range of problem sizes. In this case, we consider the asymptotic behavior  of the two functions for very large problem sizes.

next up previous contents index

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