Asymptotic Measures

From

---

Revision as of 13:31, 24 March 2009

If we are going to compare the trade-off between Time and Space, we need a system of measurement. We certainly have units by which we measure particular instances of time and space, for example, seconds and bytes. However, when we compare the time or space usage of data structures and algorithms, we are more interested in how the usage changes as the size of the problem changes. That is, what is the scalability of a data structure or an algorithm?

Therefore, we often classify the time or space usage of a data structure or an algorithm using asymptotic measures. There are six standard measures used, but we will only consider three of them. They are quite general in nature; that is, they provide bounds on the usage, and the definitions are mathematical definitions. Since a calculus background is necessary to understand the actual definitions, we will not look at the actual definitions; rather, we will just try to consider the implications of these measures.

Big-Oh

The first measure we look at, and the most commonly used, is “Big-Oh” or O( N ). This measure provided an upper bound. That is, if the time or space usage were a cost that had to be paid by money, an upper bound says that the cost will be no more than this. The cost might be less, but not more.

The parameter N in this notation is some measure of the size of the problem. This might be the number of objects in a list that needs to be sorted, or it might be the number of bits needed to represent a number. These measures are called asymptotic—related to the mathematical concept of a limit line—because we are interested in large values of N. This means that the time or space needed to sort a list of 5 objects is not really of interest. But, the time or space needed to sort 100,000 objects or 100,000,000 is of interest. Further, we are not interested in the evaluation of a particular value of N; rather, we want to know how O( N ) changes as the value of N grows very large.

Because we are interested in the relationship between N and O( N ) as N grows, the relationship is normally expressed as a function of N: O( f( N ) ). Typical functions used are the following: O( 1 ) [constant], O( log N ) [logarithmic], O( N ) [linear], O( N2 ) [quadratic], O( N log N), and O( eN ) [exponential]. Constant means that the time or space usage does not change as the size of the problem grows. Linear means that the time or space usage is directly proportional to the problem size. That is, if the size of the problem doubles, the time or space usage also doubles. In addition to quadratic, a polynomial relationship is any relationship where the base is N and the exponent is a number: N3, N4, etc. As a basic guide, any time or space usage that is polynomial or less is considered practical, while any usage that is exponential is considered not usable. For example, the Towers of Hanoi puzzle is exponential: it takes 2N -1 moves to solve the puzzle for N rings. Suppose you could move 1 ring a second. You could solve a three ring puzzle in 7 seconds or a 4 ring puzzle in 15 seconds. How long would it take you to solve a 64 ring puzzle? It would take you over one-half a trillion years!

In addition, it is very important to remember that these asymptotic measures represent rates of growth, not particular values. For example, suppose I have two measures of time, T1 and T2, where T1 is logarithmic [T1( N ) = O( log2 N )] and T2 is quadratic [T2( N ) = O( N2 )]. Note that T2 grows at a faster rate than T1: for N = 2, 4, 8, and 16, T1( N ) = 1, 2, 3, and 4 but T2( N ) = 4, 16, 64, and 256. For some particular value of N or perhaps for many small values of N, T2( N ) may actually be a smaller value. This is because we drop coefficients in the mathematical expressions for asymptotic measures.

Big-Omega

The second asymptotic measure that we will look at is Big-Omega ( Ω( N ) ) . Big- Omega is similar to Big-Oh, except it is used to represent a lower bound. That is, it is a statement that a particular time or space usage will always be at least a certain amount. It may be more, but it will not be less. Another basic difference between Big-Oh and Big- Omega is that Big-Oh represents the upper bound of a particular data structure or algorithm; whereas, Big-Omega represents the lower bound for any data structure or algorithm that solves the particular problem, even a data structure or an algorithm that might not be invented yet. As you might expect, proving a lower bound is much more difficult than proving an upper bound.

Big-Theta

The third asymptotic measure to be considered is Big-Theta ( Θ( N ) ). A problem with Big-Oh and Big-Omega is the following. Suppose I am in the market for a brand new Ford Explorer. Well, I can check at car dealerships all around the state for prices. Is it true to say that an upper bound on a new Explorer is $1,000,000? That it may cost me less, but it is not going to cost me more than $1,000,000? Is it also true to say that a lower bound on a new Explorer is $0.01? Than it may cost me more, but it will not cost me less than $0.01? Both of the figures above are valid upper and lower bounds; however, they are not very useful upper and lower bounds. When the same expression can be used for both an upper and a lower bound, for example if the time usage of an IS 320 page 4 Revision: 4/2/2008 algorithm is both O( N ) and Ω( N ), then we say it is Θ( N ). This means that Big-Theta represents a tight bound, one that is close to the actual value and is reasonable to use. However, at some point, T2( N ) will always be larger than T1( N ).