7 - Asymptotics

Summary

In this chapter, we study the rate of growth of positive sequences. We introduce a formal definition that enables us to say that one sequence does not grow faster than another sequence. Suppose we have two sequences and. We could say that x_i does not grow faster than yi if x_i ≤ y_i for every i. However, such a restricted definition is rather limited, as suggested by the following examples:

1. The sequence x_i is constant: x_i = 1000 for every i, while the sequence y_i is defined by y_i = i. Clearly we would like to say that y_i grows faster than x_i even though y₁₀₀ < x₁₀₀.

2. The sequences satisfy x_i = y_i + 5 or x_i = 2 · y_i for every i. In this case, we would like to say that the two sequences grow at the same rate even though x_i > y_i.

Thus we are looking for a definition that is insensitive to the values of finite prefixes of the sequence. In addition, we are looking for a definition that is insensitive to addition or multiplication by constants. This definition is called the asymptotic behavior of a sequence.

ORDER OF GROWTH RATES

Consider the Fibonacci sequence. The exact value of g(n), or an analytic equation for g(n), is interesting but sometimes all we need to know is how fast does g(n)grow?