Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline58050 and tex2html_wrap_inline58052, 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_inline58050 and tex2html_wrap_inline58052 to determine which algorithm is the best!

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

In the general case, we have no a priori knowledge of the problem size. However, if it can be shown, say, that tex2html_wrap_inline58074 for all tex2html_wrap_inline58076, 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.