Big O notation

Dominant terms, the orders of complexity from O(1) to O(2^n), deriving complexity from code, best, average and worst case, and space complexity.

A5.2Algorithms and complexityA level25 min

The last lesson counted operations as a function of n. Big O notation is the shorthand for that function's growth. It throws away the detail that stops mattering when n is large, and keeps the one thing that does: the shape of the curve.

Keep the dominant term, drop the constants

Suppose an algorithm makes 3n² + 5n + 20 operations. Look at how much of that total comes from the 3n² term:

As n grows the n² term swamps the others, so they are dropped. The constant 3 is dropped too: it depends on how you count an "operation" and how fast the machine is, and it does not change how the work grows. Doubling n still multiplies the work by about 4 whatever the constant. So the algorithm is O(n²), read "order n squared".

Two rules:

1. Keep only the dominant term (the one that grows fastest).
2. Remove any constant factor from it.

So 4n + 100 is O(n), 7 is O(1), n³ + 1000n² is O(n³), and 5 × 2ⁿ + n⁴ is O(2ⁿ).

The orders you need

(O(n!) is even worse than exponential: trying every order, as in the last lesson.)

Deriving the complexity of code

You can read the order straight off the structure of an algorithm:

• Statements in sequence: add their costs, then keep the biggest.
• A loop that runs n times around a body costing f: n × f.
• Nested loops, each over the n items: n × n = O(n²).
• A loop that halves what is left each time: O(log n).
• A recursive call that makes two calls on a problem one smaller: the calls double at each level, O(2ⁿ).

Here is each one in OCR's Exam Reference Language:

function first(items)          // O(1): one step, whatever the length
    return items[0]
endfunction

function total(items)          // O(n): the loop body runs n times
    sum = 0
    for i = 0 to items.length - 1
        sum = sum + items[i]
    next i
    return sum
endfunction

function halvings(n)           // O(log n): n halves each time round
    count = 0
    while n > 1
        n = n DIV 2
        count = count + 1
    endwhile
    return count
endfunction

The count of steps is what matters, not the count of lines. total is no longer than halvings, but for n = 1,000,000 its loop runs a million times and the loop in halvings runs 19 times.

Exponential growth in code

The robot has n sensors, each of which can be on or off. How many settings are there? Each sensor doubles the number, so 2ⁿ. A recursive function that builds every setting shows the doubling:

def settings(n):
    """Every on/off setting for n sensors, as strings of 0s and 1s."""
    if n == 0:
        return [""]                          # one setting of no sensors: the empty one
    shorter = settings(n - 1)
    return ["0" + s for s in shorter] + ["1" + s for s in shorter]

print(settings(3))
for n in [4, 8, 12, 16]:
    print(n, "sensors:", len(settings(n)), "settings")

Run this in the simulator

Each extra sensor doubles the work. At 16 sensors there are 65,536 settings; at 64 there would be more than 18 billion billion, far beyond any computer. Any algorithm that has to look at every subset of its input is O(2ⁿ).

Best, average and worst case

The same algorithm can take very different times on different data of the same size. Linear search for a target in n items:

• best case: the target is first. 1 comparison, O(1).
• worst case: the target is last, or not there. n comparisons, O(n).
• average case: if the target is there and equally likely to be anywhere, about n/2 comparisons, which is still O(n).

When a question gives one Big O for an algorithm without saying which case, it normally means the worst case, because that is the guarantee: the algorithm will never be slower than this.

Space complexity

Big O describes memory too. Space complexity counts the extra memory an algorithm needs as n grows, not counting the input itself.

• An algorithm that sorts inside the list it was given, using a few variables, is in place: O(1) extra space.
• One that builds a new list of the n items needs O(n) space.
• A recursive algorithm uses a stack frame for every call still waiting to finish, so recursion d calls deep needs O(d) space, even if each frame is small (module A2).

Task: count the steps

Each function in the starter has one line marked # the step. Change each function so that, instead of its answer, it returns the number of times its step ran. Then, for n = 8, 16 and 32, call each function on list(range(n)) (a list of n different numbers; halvings takes the number n itself) and print one line per function in exactly this form, with the three counts and then the order of growth:

• first: <count for 8> <count for 16> <count for 32> O(1)
• total: ... O(n)
• has_duplicate: ... O(n^2)
• halvings: ... O(log n)

Count the step in first as running once. Do not type the counts in: the program must work them out.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def first(items):
    return items[0]                               # the step

def total(items):
    s = 0
    for x in items:
        s = s + x                                 # the step
    return s

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

def halvings(n):
    count = 0
    while n > 1:
        n = n // 2                                # the step
        count = count + 1
    return count

Challenges

1. Give the Big O of 6n log n + 2n + 9, and of n² + 2ⁿ.
2. Write an O(n³) function in pseudocode and explain how you know its order.
3. Linear search's best case is O(1). Why does that not make it an O(1) algorithm?