Growth Rate

We have spent this chapter computing Big-Ohs. Linear search is $O (n)$ , binary search is $O (lo g n)$ , selection sort is $O (n^{2})$ . The Big-Oh is a group name for a family of functions that share a growth rate.

Take $O (n)$ . When we found that linear search is $O (n)$ , we dropped the constant and the lower-order terms. So a step count of $3 n + 3$ became $O (n)$ . A step count of $0.34 n$ would also become $O (n)$ . So would $234234 n$ . So $O (n)$ is not naming one function. It is naming a family of functions. Every member of the family, once you drop its constant and lower-order terms, grows in proportion to $n$ . What they share is how they respond to a bigger input: double the input and the work roughly doubles. When we call an algorithm $O (n)$ , we are saying it scales that way.

Sharing a growth rate is not the same as doing the same amount of work. An algorithm that does $2 n$ steps does more work than one that does $n$ steps, which does more than one that does $n /2$ steps. At every input size, the $2 n$ algorithm is doing twice the work of the $n$ one. That difference in the constant is a real difference and it may matter depending on the task at hand. But the difference in the constant is tiny compared to the difference between families.

Compare $2 n$ , $n$ , and $n /2$ with an $O (n^{2})$ algorithm. At a million elements, we saw in an earlier section that a step count of $n$ costs about a second while a step count of $n^{2}$ costs about twelve days. Doubling or halving the linear one changes its cost to between half a second and two seconds. The quadratic one still costs about twelve days. Inside the family, the difference is a factor of two or four. Between the families, the difference keeps growing as $n$ grows, with no bound on it.

At small $n$ , the constant can decide which algorithm does less work. But $n^{2}$ eventually outgrows $c n$ for any constant $c$ you pick, so there is always an input size past which the quadratic algorithm does more work. So the family decides which algorithm wins for large inputs. The constant only decides what input size we have to get to before that happens.