Lesson 7.4

Best, average and worst case

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

Best, average and worst case

By the end of this you will be able to describe the input that gives an algorithm its best case and its worst case, count the steps in each, and say which case a Big O answer is usually about.

How it is asked

The new course has had no exams yet (the first are in May 2027), so there is no pattern of past questions to point to. The syllabus asks you to tell the three cases apart, and the natural way to ask that is as one part of a question about an algorithm you have just been given or asked to write, usually a search or a sort:

Describe the input that gives the best case, or the worst case.
State how many comparisons that case makes for a list of n values.
State the Big O of the worst case, or explain why two inputs of the same size take different times.

A good answer describes an input ("the target is the first value"), not a size ("a short list"). Mixing the two up is the easiest slip to make here, and this lesson is about avoiding it.

Key idea: Best and worst case compare different inputs of the same size n.

Same size, different work

Here is a loop that looks for a name in a list. It stops as soon as it finds it. Step through it: the name it wants is the very first one.

Step through it

names = ["Ana", "Ben", "Cai", "Dev", "Eli"]

target = "Ana"

i = 0

checks = 0

found = False

while i < len(names) and not found:

checks = checks + 1

if names[i] == target:

found = True

i = i + 1

print(checks)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/12

The target is the first name, so the loop stops after one comparison: the best case.

Now the same loop, with the same five names, looking for a name that is not there.

Step through it

names = ["Ana", "Ben", "Cai", "Dev", "Eli"]

target = "Zoe"

i = 0

checks = 0

found = False

while i < len(names) and not found:

checks = checks + 1

if names[i] == target:

found = True

i = i + 1

print(checks)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/27

Same list, same size, a different target: five comparisons instead of one.

Nothing about the list changed. Its size is 5 both times. What changed is the input that decides where the loop stops.

The three cases

For a fixed size n:

The best case is the input of that size that takes the fewest steps. Here, the target is the first name: 1 comparison.
The worst case is the input of that size that takes the most steps. Here, the target is the last name, or not in the list at all: n comparisons.
The average case is the number of steps you expect over all inputs of that size, taken as equally likely.

Quick check

Which input gives this loop its best case for a list of n names?

How it is marked

Here is an exam-style question of our own about the loop above, with a mark for each point an examiner would look for. Switch to the second script to see where marks go.

How it is marked

The loop above looks for a target in a list of n names. (a) Describe the best case and state how many comparisons it makes. [2] (b) Describe the worst case and state its Big O complexity. [2]

[4]

(a) The target is the first name in the list.[1]
Describes the input, for a list of any size.

So far 1 of 4

The slip script scores 2 of 4: both lost marks come from describing a size instead of an input.

The average case

If the target is in the list, and is equally likely to be at any of the n places, the loop makes 1 comparison when it is first, 2 when it is second, and so on up to n. On average that is (n + 1) / 2 comparisons, about half the list.

Quick check

A list holds 1000 names, and the target is equally likely to be any one of them. About how many comparisons does the loop make on average?

Half of n is still O(n), because Big O drops the constant factor. So for this loop the average and the worst case are in the same class, O(n), and only the best case, O(1), is different.

Which case Big O is about

When a question asks for "the complexity" of an algorithm and says nothing about cases, give the worst case. It is a promise: the algorithm will never take longer than this, whatever input it gets. A best case of O(1) does not make an algorithm O(1). It only says what happens when you are lucky.

Quick check

A student says: "The best case is one comparison, so this search is O(1)." What is wrong?

Now try it yourself on the questions below.

Exercise 7.4.17.4.1 · Answer itAll lights on cases

A building has n lights in a row, each on or off. This function checks whether they are all on. It returns as soon as it finds one that is off.

def all_on(lights):
    for light in lights:
        if not light:
            return False
    return True

public static boolean allOn(boolean[] lights) {
    for (boolean light : lights) {
        if (!light) {
            return false;
        }
    }
    return true;
}

(a) Describe the input of n lights that gives the best case. [1]

(b) Describe an input of n lights that gives the worst case. [1]

(c) A student writes: "The best case is when there are no lights, so the function is O(1)." Explain two things that are wrong with this claim. [2]

[4]

Your answer

Exercise 7.4.27.4.2 · Answer itPair sum cases

This function returns whether any two values at different positions in a list add up to total. It compares pairs, and returns as soon as it finds one that works.

def has_pair(values, total):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] + values[j] == total:
                return True
    return False

public static boolean hasPair(int[] values, int total) {
    for (int i = 0; i < values.length; i++) {
        for (int j = i + 1; j < values.length; j++) {
            if (values[i] + values[j] == total) {
                return true;
            }
        }
    }
    return false;
}

The list holds n values, where n is at least 2. Count one comparison each time the if is checked.

(a) Describe the input that gives the best case, and state how many comparisons it makes. [2]

(b) State how many comparisons the worst case makes when n is 5. [1]

[4]

Your answer

Report a problem with this page