Asymptotic analysis

We would like to classify functions based on the order of their growth. Function \(f(n) = 3n^2\) and \(g(n) = 2n^2 + n + \log(n)\) are different but in a sense the same when you consider the order of their growth. More concretely, they both satisfy the equation \(\lim_{n \to \infty} h(2n)/h(n) = 4\). We can think of \(f\) and \(g\) as time taken by some algorithms. Then, the limit communicates the information that if we double the size of the input, the running time increases by a factor of four.

Running times are functions on natural numbers. We can only take limits of continuous functions on real numbers. So to do the above analysis, we need to develop a new theory to measure the order of growth of functions on natural numbers. This theory is called asymptotic analysis of discrete functions. The fundamental question answered by this theory is: Given functions \(f\) and \(g\), how is the order of growth of \(f\) related to the order of growth of \(g\)?

We use \(O(f)\) to denote the set of all functions that grow at most as fast as \(f\). We want to define \(O(.)\) so that we can make assertions like \(2n^2 + n + \log(n) \in O(n^3)\), which should be read as: “The function \(g(n) = 2n^2 + n + \log(n)\) grows at most as fast as \(n^3\)”. This is true because the value of \(g\) increases by four times when \(n\) doubles whereas the value of \(n^3\) increases by eight times when \(n\) doubles. So as \(n\) grows larger, the value of \(n^3\) will eventually be larger, and stay larger, than that of \(g(n)\). We also want to assert that \(1000n^3 \in O(n^3)\) because even though the value of \(n^3\) can never be larger than that of \(1000n^3\), the rate of growth of \(1000n^3\) is at most that of \(n^3\).

\begin{align*} O(f) &= \{ g \mid \exists [n_0, c > 0](\forall [n \geq n_0](g(n) \leq cf(n)))\} \\ \Omega(f) &= \{ g \mid \exists [n_0, c > 0](\forall [n \geq n_0](g(n) \geq cf(n)))\} \\ \Theta(f) &= O(f) \cap \Omega(f) \end{align*}

Exercise #

  1. The Fibonacci sequence is given by the recurrence: \(F_0=F_1=1\), \(F_n=F_{n-1} + F_{n-2}\) for \(n>2\). What is the largest Fibonacci number that can fit into a word in a 64-bit machine? What about 128-bit machines?