Lesson 7.2

Common complexity classes

Part 7: AlgorithmsReading, about 7 min2 exercises in this lesson

Big O complexity classes: O(1), O(log n), O(n), O(n²)

By the end of this you will be able to state what the four common complexity classes mean, constant, logarithmic, linear and quadratic, and say how each one's steps grow when the input gets bigger.

Start with a strange kind of work: take a number and halve it, again and again, until it reaches 1. Throw away any half left over, as whole-number division does. Here it is for 1000.

1000 → 500 → 250 → 125 → 62
  → 31 → 15 → 7 → 3 → 1

That is 9 halvings. Now try 2000. The first halving gives 1000, and from there it is the same 9 again, so 2000 takes 10. Doubling the input added just one step. Of the kinds of growth in this lesson, only work that does not grow at all is better.

Big O names how the steps grow

In the last lesson you counted steps against the size of the input, n. Big O notation is a short way to say how that count grows. You write a capital O and, in brackets, the kind of growth: O(n) is said "order n" or "big O of n".

Big O gives an upper bound on growth: the steps grow no faster than this as n gets large. It leaves out the details that do not change the kind of growth. An algorithm that takes 3n steps and one that takes n steps are both O(n), because doubling n doubles both of them. Because it is an upper bound, an O(n) algorithm is, strictly, also O(n²): its steps grow no faster than n² either. That says less than you know, so when you give a class, give the smallest one that fits.

The four common classes

O(1), constant time. The number of steps does not depend on n. Reading the first value of a list takes one step however long the list is, and so does the formula for adding 1 to n from the last lesson.
O(log n), logarithmic time. Each step cuts what is left in half, so doubling n adds about one step. Here log n is the logarithm to base 2, which is close to the number of times you can halve n before you reach 1: about 10 for n = 1000, and about 20 for n = 1000000. Counting halvings with whole-number division gives a little less, 9 for 1000, because each halving throws away what is left over.
O(n), linear time. The steps grow in proportion to n. Looking at each value in a list once is O(n): double the list, and the steps double.
O(n²), quadratic time. The steps grow in proportion to n times n. Pairing every value in a list with every value, itself included, makes n times n pairs: double the list, and the steps go up four times.

Here are the step counts for the example given for each class above.

Class	n = 10	n = 100	n = 1000	When n doubles
O(1)	1	1	1	the same
O(log n)	3	6	9	one more
O(n)	10	100	1000	twice as many
O(n²)	100	10000	1000000	four times as many

Read down the n = 1000 column. The quadratic example takes a million steps where the logarithmic one takes 9. For large inputs, the classes from best to worst are O(1), O(log n), O(n), O(n²).

Counting halvings yourself

This program halves each of 10, 100 and 1000 until it reaches 1, and counts the halvings.

for n in [10, 100, 1000]:
    size = n
    halvings = 0
    while size > 1:
        size = size // 2
        halvings = halvings + 1
    print(str(n) + ": " + str(halvings))

public static void main(String[] args) {
    int[] sizes = {10, 100, 1000};
    for (int n : sizes) {
        int size = n;
        int halvings = 0;
        while (size > 1) {
            size = size / 2;
            halvings = halvings + 1;
        }
        System.out.println(
            n + ": " + halvings);
    }
}

It prints:

10: 3
100: 6
1000: 9

The input grew 100 times, from 10 to 1000, but the halvings only went from 3 to 9. That is what logarithmic growth looks like.

What Big O does not tell you

Big O is about how the steps grow for large n. It is not a time in seconds, and it is not an exact step count.

Two O(n) algorithms can differ: one may take 2n steps and the other 50n. Big O puts them in the same class because both grow in proportion to n.
For a small input, an algorithm whose steps grow like n² can finish sooner than one whose steps grow like n but that does a lot of work per value. Once n is large enough, the one that grows like n² always falls behind.

Now try it yourself on the questions below.

Exercise 7.2.17.2.1 · Answer itName the growth

Four algorithms, W, X, Y and Z, were each run on an input of size 100 and then of size 200. The table shows how many steps each one took. Each time n doubles again, each algorithm's steps change in the same way as they did from 100 to 200.

Algorithm	Steps for n = 100	Steps for n = 200
W	300	600
X	8	8
Y	10000	40000
Z	6	7

(a) State the smallest Big O class that fits each algorithm, choosing from O(1), O(log n), O(n) and O(n²). [4]

(b) State how many steps Y would take for n = 400. [1]

[5]

Your answer

Exercise 7.2.27.2.2 · Answer itWord finder growth

Three apps look up a word in a dictionary of n words. App P is O(n), app Q is O(log n) and app R is O(1). Assume each app's steps grow exactly as its class says.

(a) State what happens to the number of steps app P takes when n doubles. [1]

(b) State what happens to the number of steps app Q takes when n doubles. [1]

(d) The dictionary grows from 1000 words to 1000000 words, which is 1000 times as many. Explain which of apps P and Q copes better with this growth, using how the steps of each one change. [2]

[5]

Your answer