Reading Big-Oh from Code

We have the notation now, and we have the two rules that go with it: suppress the coefficients, drop the lower-order terms. So far we have applied those rules to a step count we worked out by hand, turning an expression like $\alpha n+\beta$ into $O(n)$.

In practice we almost never count steps. Once you know what the two rules do to a step count, you can look at the code, reason about how its work grows, and name the Big-Oh without writing down a step count.

The procedure is the same every time. Find where most of the work happens, which is usually a loop or a nest of loops. Then ask how many times that work runs as the input grows. Constant work repeated $n$ times is $O(n)$. Constant work repeated $n^2$ times is $O(n^2)$. The number of operations in the loop body affects only the coefficient, and we suppress the coefficient anyway, so we do not have to count them. The next few sections are worked examples of this procedure.

Before you write the Big-Oh for an algorithm, you must figure out what the input size is because the Big-Oh is a function of that size.

In every example so far except one, the size of the input has been the length of the array we passed in, and we denote it by $n$. That is the usual case when we study data structures: the size of the input is the number of elements the structure holds. But it is not always the case.

The one exception so far is the countUp method. It takes a single integer num and loops num times. We still used $n$ to denote the value of num, but that is the value of a single integer, and the work grows with that value.