Lesson 7.3

Big O from loop structure

Part 7: AlgorithmsReading, about 8 min3 exercises in this lesson

Big O from loops: nested, one after another, halving

By the end of this you will be able to work out the Big O class of a short piece of code by looking at its loops: how many there are, whether one sits inside another, and how each counter changes.

Here are two loops, one inside the other, both counting from 0 up to n. Watch how often the inner body runs for n = 3.

i = 0   j takes 0, 1, 2   body runs 3
i = 1   j takes 0, 1, 2   body runs 3
i = 2   j takes 0, 1, 2   body runs 3
             in all, 3 × 3 = 9 runs

For every turn of the outer loop, the inner loop runs all of its turns. So the body runs n times n. You can check that for bigger n.

for n in [10, 100, 1000]:
    runs = 0
    for i in range(n):
        for j in range(n):
            runs = runs + 1
    print(str(n) + ": " + str(runs))

public static void main(String[] args) {
    int[] sizes = {10, 100, 1000};
    for (int n : sizes) {
        int runs = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                runs = runs + 1;
            }
        }
        System.out.println(
            n + ": " + runs);
    }
}

It prints:

10: 100
100: 10000
1000: 1000000

Each time n grows 10 times, the runs grow 100 times. That is n², so two loops nested like this are O(n²).

The method

Find the line that runs most often. It is usually in the innermost loop.
Count how many times it runs, in terms of n.
Drop constant factors and every smaller term, and keep the part that grows fastest. That part, inside O( ), is the answer.

Step 3 is what Big O means. It gives an upper bound on how the steps grow as n gets large, so 5n and n are both O(n), and n² + n is O(n²).

Loop shapes to know

When the class is not obvious, compare the code with these shapes.

No loop. A few lines that run once each take the same number of steps for any n. That is O(1). A line such as a single addition, or reading one value from a list by its position, counts as one step.
One loop over n. A loop that runs n times, with a body that does a fixed number of steps, is O(n). A loop that runs 2n times, or n / 2 times, is O(n) too, because dropping the constant leaves n.
A loop inside a loop. Multiply the turns. Outer n times inner n is n², so O(n²). But look at the inner loop before you multiply. If it always runs a fixed number of times, such as 7 for the days of a week, the body runs 7n times, which is O(n). A loop inside a loop is not always O(n²).
An inner loop that changes length. Sometimes the inner loop runs a different number of times on each turn, shorter or longer than n. Then add up the turns it really makes. If, on average, it runs about half of n, the total is about n² / 2, and dropping the half still leaves O(n²).
Loops one after another. Add them. A loop of n, then a nested loop of n², is n + n² steps. Keep the term that grows fastest: O(n²). At n = 1000 the single loop adds 1000 steps to 1000000, which is a tenth of one percent.
A counter that halves. If the counter is halved on every turn, as with the halving loop in the last lesson, the loop runs about log n times, so it is O(log n). The same goes for a counter that doubles on every turn until it reaches n. In Python the halving is written with //, and in Java with / on whole numbers, which also throws away the remainder.

Writing the answer

A question that asks for the Big O of some code usually wants two things: the class, and the reason from the loops. For the nested program above you could write: the outer loop runs n times, and for each of those the inner loop runs n times, so the body runs n × n times. That is O(n²).

Saying only "it has two loops, so it is O(n²)" is not a reason. Two loops over n, one after the other, are O(n), and a loop inside a loop with a fixed inner count is O(n) too. Say how many times each loop runs.

Now try it yourself on the questions below.

Exercise 7.3.17.3.1 · Answer itHandshake count

At a meeting of n people, everyone shakes hands once with everyone else. Each new person shakes hands with everyone already counted. This function counts the handshakes, one turn of the inner loop for each.

def handshakes(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count = count + 1
    return count

public static int handshakes(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            count = count + 1;
        }
    }
    return count;
}

(a) State the value the function returns when n is 6. [1]

(b) State the Big O complexity of the function. [1]

(c) The inner loop does not run n times on every turn of the outer loop. Explain why the function still has the complexity you gave in (b). [2]

[4]

Your answer

Exercise 7.3.27.3.2 · Answer itTournament rounds

In a knockout contest, half of the players are out after each round. This function works out how many rounds are needed for a number of players, a whole number from 1 to 1000000.

def rounds(players):
    count = 0
    size = 1
    while size < players:
        size = size * 2
        count = count + 1
    return count

public static int rounds(int players) {
    int count = 0;
    int size = 1;
    while (size < players) {
        size = size * 2;
        count = count + 1;
    }
    return count;
}

(a) State the value the function returns for 16 players. [1]

(b) State the Big O complexity of the function, where n is the number of players. [1]

[4]

Your answer

Exercise 7.3.37.3.3 · Answer itLoops in a row

Each of these two functions takes a whole number n from 1 to 1000 and returns how many times the line total = total + 1 ran (in Java, total = total + 1;).

Function A:

def hours_in(n):
    total = 0
    for day in range(n):
        for h in range(24):
            total = total + 1
    return total

public static int hoursIn(int n) {
    int total = 0;
    for (int day = 0; day < n; day++) {
        for (int h = 0; h < 24; h++) {
            total = total + 1;
        }
    }
    return total;
}

Function B:

def two_parts(n):
    total = 0
    for i in range(n):
        total = total + 1
    for i in range(n):
        for j in range(n):
            total = total + 1
    return total

public static int twoParts(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total = total + 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            total = total + 1;
        }
    }
    return total;
}

(a) State the value function A returns when n is 10. [1]

(b) State the Big O complexity of function A. [1]

(d) State the Big O complexity of function B. [1]

(e) Explain why the first loop in function B does not appear in your answer to (d). [1]

[5]

Your answer