NZ NCEA Level 3 Digital Technologies

Why running time is not the measure

Timing a program with a stopwatch says as much about the computer as about the algorithm. A slow algorithm on a fast machine can beat a fast algorithm on a slow one, and the result changes with the language, the compiler, what else is running and the particular input. Computer scientists therefore measure an algorithm by how the amount of work it does grows as the input grows. The input size is written $n$: the number of items in a list, the number of cities in a route, the number of digits in a number.

Work is counted in basic steps, such as a comparison, an assignment or an arithmetic operation, each treated as taking one unit of time. The count is a function of $n$, and what matters is the shape of that function for large $n$. This is time complexity. Space complexity is the same idea applied to memory: how much extra storage the algorithm needs as $n$ grows, not counting the input itself.

Counting steps

Consider a function that finds the largest value in a list of $n$ numbers.

def largest(items):
    best = items[0]
    for x in items[1:]:
        if x > best:
            best = x
    return best

The loop runs $n - 1$ times and each pass does one comparison and possibly one assignment. The total is roughly $2n$ steps at most, plus a constant for the set-up. Doubling the list doubles the work. Whether the exact figure is $2n$ or $3n + 5$ does not change that, which is why the constants are dropped.

Now a function that checks whether any two numbers in a list are equal by comparing every pair.

def has_duplicate(items):
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

The inner loop runs $n-1$ times for $i = 0$, then $n-2$, and so on down to zero. The number of comparisons in the worst case is

For $n = 10$ this is 45 comparisons, for $n = 100$ it is 4,950 and for $n = 1{,}000$ it is 499,500. Multiplying $n$ by ten multiplies the work by about a hundred, which is the signature of work proportional to $n^2$.

Big O notation

Big O notation describes an upper bound on how fast the number of steps grows. Writing $f(n) = O(g(n))$ means that for large enough $n$, $f(n)$ is no bigger than some constant multiple of $g(n)$. In practice two simplifications give the answer.

1. Drop constant factors. $3n$ and $50n$ are both $O(n)$.
2. Keep only the term that grows fastest. $n^2 + 5n + 100$ is $O(n^2)$, because for large $n$ the $n^2$ term swamps the others.

So the duplicate check above is $O(n^2)$ and the largest-value function is $O(n)$. Big O says nothing about small inputs: $100n$ is $O(n)$ and $n^2$ is $O(n^2)$, yet $n^2$ is the smaller of the two until $n$ passes 100. Big O is a statement about what happens as the input grows without limit.

Base of a logarithm does not matter inside Big O, because changing base multiplies by a constant. $O(\log_2 n)$ and $O(\log_{10} n)$ are the same class and are written $O(\log n)$.

Common growth rates

The table is in order of increasing growth. The jump from polynomial rates ($n$, $n^2$, $n^3$) to exponential and factorial rates is the dividing line the rest of this topic is built on.

How fast the rates grow

The table below shows the number of steps for a few sizes, assuming one step per unit.

A computer doing a billion steps a second takes about a second for $2^{30}$ steps, but $2^{100}$ steps would take far longer than the age of the universe. Making the computer a thousand times faster changes that only by three orders of magnitude out of thirty. This is why an exponential algorithm is described as unusable for large inputs whatever hardware it runs on, while a polynomial one can be rescued by faster hardware.

Logarithmic growth is the opposite extreme. Binary search on a sorted list of 1,000,000 items needs at most 20 comparisons, because $2^{20} = 1{,}048{,}576$ is the first power of two above a million. Doubling the list to 2,000,000 items adds one comparison.

Reading complexity from code

A few patterns cover most cases.

• A single loop from 1 to $n$ doing constant work inside is $O(n)$.
• A loop nested inside another, both running to $n$, is $O(n^2)$.
• A loop in which the control variable is halved or doubled each pass (while i < n: i = i * 2) is $O(\log n)$.
• A loop over $n$ items that calls an $O(\log n)$ operation each time, such as a binary search, is $O(n \log n)$.
• Steps done one after another add, and the larger term wins: an $O(n)$ pass followed by an $O(n^2)$ pass is $O(n^2)$.
• A loop whose bound does not depend on the input (run exactly 1,000 times) is $O(1)$.

Recursion is analysed by how many calls are made and how much work each does. A recursive function that calls itself twice on inputs only one smaller, like the naive Fibonacci below, makes a number of calls that roughly doubles with each increase in $n$.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The call tree for fib(5) already repeats fib(3) twice and fib(2) three times. The total number of calls grows exponentially, about $1.6^n$, so fib(50) is out of reach this way while a loop that keeps the last two values does the job in $O(n)$ steps.

Space complexity

Space complexity counts the extra memory used. The largest-value function uses a few variables whatever the size of the list, so it is $O(1)$ in space. Merge sort needs a second array to merge into, so it uses $O(n)$ extra space. A recursive function that goes $n$ calls deep uses $O(n)$ space for its call stack even if it stores nothing else.

Time and space often trade against each other. Storing results already calculated (memoisation) removes the repeated work in the Fibonacci example, turning exponential time into linear time at the price of $O(n)$ memory.

Other bounds

Big O is an upper bound, and two companions exist for completeness. Big Omega, $\Omega(g(n))$, is a lower bound: the algorithm takes at least this much. Big Theta, $\Theta(g(n))$, says both hold, so the growth is exactly of that order. Saying a linear search is $O(n^2)$ is technically true but uninformative; the useful statement is the tightest bound, and for searching an unsorted list that is $\Theta(n)$ in the worst case.