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_inline58251 and tex2html_wrap_inline58253, 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_inline58251 and tex2html_wrap_inline58253 to determine which algorithm is the best!

But is it really that simple? What exactly does it mean for one function, say tex2html_wrap_inline58251, to be better than another function, tex2html_wrap_inline58253? One possibility arises if we know the problem size a priori. For example, suppose the problem size is tex2html_wrap_inline58265 and tex2html_wrap_inline58267. Then clearly algorithm A is better than algorithm B for problem size tex2html_wrap_inline58265.

In the general case, we have no a priori knowledge of the problem size. However, if it can be shown, say, that tex2html_wrap_inline58275 for all tex2html_wrap_inline58277, 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 © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.