7.2.1 Big O

The first notation we introduce is $O$, pronounced “big oh”. The $O$ function takes as input a function, and produces as output the set of all functions that grow no faster than the input function. The set $O(f)$ is the set of all functions that grow as fast as, or slower than, $f$ grows. In Figure 7.2, the $O(f)$ set is represented by everything inside the outer circle.

To define the meaning of $O$ precisely, we need to consider what it means for a function to grow. We want to capture how the output of the function increases as the input to the function increases. First, we consider a few examples; then we provide a formal definition of $O$.

$f(n) = n + 12$ and $g(n) = n - 7$
No matter what $n$ value we use, the value of $f(n)$ is greater than the value of $g(n)$. This doesn't matter for the growth rates, though. What matters is how the difference between $g(n)$ and $f(n)$ changes as the input values increase. No matter what values we choose for $n_1$ and $n_2$, we know $g(n_1) - f(n_1) = g(n_2) - f(n_2) = -19$. Thus, the growth rates of $f$ and $g$ are identical and $n - 7$ is in the set $O(n + 12)$, and $n + 12$ is in the set $O(n - 7)$.

$f(n) = 2n$ and $g(n) = 3n$
The difference between $g(n)$ and $f(n)$ is $n$. This difference increases as the input value $n$ increases, but it increases by the same amount as $n$ increases. So, the growth rate as $n$ increases is $\frac{n}{n} = 1$. The value of $2n$ is always within a constant multiple of $3n$, so they grow asymptotically at the same rate. Hence, $2n$ is in the set $O(3n)$ and $3n$ is in the set $O(2n)$.

$f(n) = n$ and $g(n) = n^2$
The difference between $g(n)$ and $f(n)$ is $n^2 - n = n (n - 1)$. The growth rate as $n$ increases is $\frac{n (n - 1)}{n} = n - 1$. The value of $n - 1$ increases as $n$ increases, so $g$ grows faster than $f$. This means $n^2$ is not in $O(n)$ since $n^2$ grows faster than $n$. The function $n$ is in $O(n^2)$ since $n$ grows slower than $n^2$ grows.

$f(n) = \mathrm{Fibonacci}(n)$ and $g(n) = n$
The $\mathrm{Fibonacci}$ function grows very rapidly. The value of $\mathrm{Fibonacci}(n+2)$ is more than double the value of $\mathrm{Fibonacci}(n)$ since

$$ \mathrm{Fibonacci}(n+2) = \mathrm{Fibonacci}(n + 1) + \mathrm{Fibonacci}(n) $$

and $\mathrm{Fibonacci}(n + 1) > \mathrm{Fibonacci}(n)$. The rate of increase is multiplicative, and must be at least a factor of $\sqrt{2} \approx 1.414$ (since increasing by one twice more than doubles the value). (In fact, the rate of increase is a factor of $\phi = (1 + \sqrt{5}) / 2 \approx 1.618$, also known as the "golden ratio". This is a rather remarkable result, but explaining why is beyond the scope of this book.) This is much faster than the growth rate of $n$, which increases by one when we increase $n$ by one. So, $n$ is in the set $O(\mathrm{Fibonacci}(n))$, but $\mathrm{Fibonacci}(n)$ is not in the set $O(n)$.

Figure 7.3:Orders of Growth

Some of the example functions are plotted in Figure 7.3 The $O$ notation reveals the asymptotic behavior of functions. The functions plotted are the same in both graphs, but the scale of the horizontal axis is different. In the first graph, the rightmost value of $n^2$ is greatest; for higher input values, the value of $\mathrm{Fibonacci}(n)$ is greatest. In the second graph, the values of $\mathrm{Fibonacci}(n)$ for input values up to 20 are so large that the other functions appear as nearly flat lines on the graph.

Definition of $O$ The function $g$ is a member of the set $O(f)$ if and only if there exist positive constants $c$ and $n_0$ such that, for all values $n \ge n_0$,

$$g(n) \le cf(n).$$

We can show $g$ is in $O(f)$ using the definition of $O(f)$ by choosing positive constants for the values of $c$ and $n_0$, and showing that the property $g(n) \le cf(n)$ holds for all values $n \ge n_0$. To show $g$ is not in $O(f)$, we need to explain how, for any choices of $c$ and $n_0$, we can find values of $n$ that are greater than $n_0$ such that $g(n) \le cf(n)$ does not hold.

Example 7.1: $O$ Examples

We now show the claimed properties are true using the formal definition.
$n-7$ is in $O(n+12)$
Choose $c = 1$ and $n_0 = 1$. Then, we need to show $n-7 \le 1(n+12)$ for all values $n \ge 1$. This is true, since $n-7 > n+12$ for all values $n$.

$n+12$ is in $O(n-7)$
Choose $c = 2$ and $n_0 = 26$. Then, we need to show $n+12 \le 2(n-7)$ for all values $n \ge 26$. The equation simplifies to $n + 12 \le 2n - 14$, which simplifies to $26 \le n$. This is trivially true for all values $n \ge 26$.

$2n$ is in $O(3n)$
Choose $c = 1$ and $n_0 = 1$. Then, $2n \le 3n$ for all values $n \ge 1$.

$3n$ is in $O(2n)$
Choose $c = 2$ and $n_0 = 1$. Then, $3n \le 2(2n)$ simplifies to $n \le 4/3 n$ which is true for all values $n \ge 1$.

$n$ is in $O(n^2)$
Choose $c = 1$ and $n_0 = 1$. Then $n \le n^2$ for all values $n \ge 1$.

$n^2$ is not in $O(n)$
We need to show that no matter what values are chosen for $c$ and $n_0$, there are values of $n \ge n_0$ such that the inequality $n^2 \le cn$ does not hold. For any value of $c$, we can make $n^2 > cn$ by choosing $n>c$.

$n$ is in $O(\mathrm{Fibonacci}(n))$
Choose $c = 1$ and $n_0 = 3$. Then $n \le \mathrm{Fibonacci}(n)$ for all values $n \ge n_0$.

$\mathrm{Fibonacci}(n)$ is not in $O(n-2)$
No matter what values are chosen for $c$ and $n_0$, there are values of $n \ge n_0$ such that $\mathrm{Fibonacci}(n) > c(n)$. We know $\mathrm{Fibonacci}(12)=144$, and, from the discussion above, that:

$$ \mathrm{Fibonacci}(n+2) > 2 * \mathrm{Fibonacci}(n) $$

This means, for $n>12$, we know $\mathrm{Fibonacci}(n)>n^2$. So, no matter what value is chosen for $c$, we can choose $n=c$. Then, we need to show

$$ \mathrm{Fibonacci}(n) > n(n) $$

The right side simplifies to $n^2$. For $n>12$, we know $\mathrm{Fibonacci}(n) > n^2$. Hence, we can always choose an $n$ that contradicts the $\mathrm{Fibonacci}(n) \le cn$ inequality by choosing an $n$ that is greater than $n_0$, 12, and $c$.

For all of the examples where $g$ is in $O(f)$, there are many acceptable choices for $c$ and $n_0$. For the given $c$ values, we can always use a higher $n_0$ value than the selected value. It only matters that there is some finite, positive constant we can choose for $n_0$, such that the required inequality, $g(n) \le cf(n)$ holds for all values $n \ge n_0$. Hence, our proofs work equally well with higher values for $n_0$ than we selected. Similarly, we could always choose higher $c$ values with the same $n_0$ values. The key is just to pick any appropriate values for $c$ and $n_0$, and show the inequality holds for all values $n \ge n_0$.

Proving that a function is not in $O(f)$ is usually tougher. The key to these proofs is that the value of $n$ that invalidates the inequality is selected after the values of $c$ and $n_0$ are chosen. One way to think of this is as a game between two adversaries. The first player picks $c$ and $n_0$, and the second player picks $n$. To show the property that $g$ is not in $O(f)$, we need to show that no matter what values the first player picks for $c$ and $n_0$, the second player can always find a value $n$ that is greater than $n_0$ such that $g(n) > cf(n)$.

Exercise 7.2 For each of the $g$ functions below, answer whether or not $g$ is in the set $O(n)$. Your answer should include a proof. If $g$ is in $O(n)$ you should identify values of $c$ and $n_0$ that can be selected to make the necessary inequality hold. If $g$ is not in $O(n)$ you should argue convincingly that no matter what values are chosen for $c$ and $n_0$ there are values of $n \ge n_0$ such the inequality in the definition of $O$ does not hold.
a. $g(n) = n + 5$
b. $g(n) = .01n$
c. $g(n) = 150n + \sqrt{n}$
d. $g(n) = n^{1.5}$
e. $g(n) = n!$

Exercise 7.3 Given $f$ is some function in $O(h)$, and $g$ is some function not in $O(h)$, which of the following must always be true:
a. For all positive integers $m$, $f(m) \le g(m)$.
b. For some positive integer $m$, $f(m) < g(m)$.
c. For some positive integer $m_0$, and all positive integers $m > m_0$,

$$ f(m) < g (m). $$