Best, average and worst case in Python

Problem

It was instant in the test

The shop's support team looks up an order by number when a customer calls. The orders of the month are in a list, in the order they came in. The colleague who wrote the search tried it with order 1001 and said: "One check. It is instant, however many orders there are."

A month later support complains: sometimes the search is fast, sometimes it is slow. It is slowest when the customer gets the number wrong and there is no such order.

Both are true. The same search makes one check or it makes all of them. So how fast is it? Which number do you tell support?

The idea

Three cases of one algorithm

The number of operations depends not only on n, but also on what the input is. So we look at three cases:

the best case: the input with the least work. Here the order you want is the first one;
the worst case: the input with the most work. Here the order is the last one or it is not there;
the average case: how much work there is on average if the inputs follow some rule, usually "every one is equally likely".

The colleague measured the best case and said O(1). But linear search is O(n): with n orders the checks can be n.

See it

The search with a counter

The search checks the orders one by one and stops when it finds the number:

checks = 0


def find_order(ids, wanted):
    global checks
    for i in range(len(ids)):
        checks += 1
        if ids[i] == wanted:
            return i
    return -1

report resets the counter, searches, and prints the index (-1 if the order is not there) and the checks:

def report(ids, wanted):
    global checks
    checks = 0
    at = find_order(ids, wanted)
    print(f"{wanted}: {at}, checks: {checks}")

Three searches in 1,000 orders: the first one, the one in the middle and a number that is not there:

ids = [1001 + k for k in range(1000)]
report(ids, 1001)
report(ids, 1501)
report(ids, 999)

1001: 0, checks: 1
1501: 500, checks: 501
999: -1, checks: 1000

See it

One search, three cases

checks = 0


def find_order(ids, wanted):
    global checks
    for i in range(len(ids)):
        checks += 1
        if ids[i] == wanted:
            return i
    return -1


def report(ids, wanted):
    global checks
    checks = 0
    at = find_order(ids, wanted)
    print(f"{wanted}: {at}, checks: {checks}")


ids = [1001 + k for k in range(8)]
report(ids, 1001)
report(ids, 1005)
report(ids, 999)

Step by step, in words

8 orders of the month, numbered 1001 to 1008 in the order they came in. The search goes from the start, one by one.
The best case: the order is the first one. 1 check, and the search is over. Output: 1001: 0, checks: 1.
The order is in the middle: 5 checks, n/2 + 1. Output: 1005: 4, checks: 5.
The worst case: there is no such order. The search checks all 8 and only then returns -1. Output: 999: -1, checks: 8.
The average case: if every order is searched for equally often, the checks are 1, 2, …, 8. On average (1 + … + 8) / 8 = 4.5: about n/2. Still O(n).
What we promise is the worst case: at most n checks, whatever they search for. Linear search is O(n).

The same 8 orders, the same search. The only difference is what you search for.

The idea

Why we promise the worst case

The best case says nothing. Almost any algorithm is fast if the input suits it. Promising the best case means counting on luck.

The worst case is a promise. "At most n checks, whatever they search for." You plan with that number: how many orders support can search before the page gets slow. So when people say "linear search is O(n)", they mean the worst case.

The average case is useful, but it needs an assumption. If every order is searched for equally often (random input), searching for each one once gives the average:

ids = [1001 + k for k in range(1000)]
total = 0
for wanted in ids:
    checks = 0
    find_order(ids, wanted)
    total += checks
print("Total: " + str(total))
print("Average: " + str(total / len(ids)))

Total: 500500
Average: 500.5

(1 + 2 + … + 1,000) / 1,000 = 500.5: about n/2. The constant ½ does not change the class: the average case is O(n) too. But if people mostly search for new orders, or mostly for wrong numbers, the average is different. The assumption about the input is part of the answer.

Run the three cases in Bench:

The order is the first one O(1)
The order is in the middle O(n)
There is no such order O(n)

Algorithm	n = 10	n = 1,000	n = 100,000
The order is the first one	1	1	1
The order is in the middle	6	501	50,001
There is no such order	10	1,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

More precisely, if you are curious

The built-in search in a list is the same linear search. ids.index(wanted) and wanted in ids walk the elements one by one: O(n) in the worst case. Unlike the other languages, index does not return -1, it raises ValueError if the element is not there.

When the average and the worst case are very different. Some algorithms are fast almost always, and on rare inputs they get much slower. Quick sort is O(n log n) on average, and with a bad choice of the pivot it becomes O(n²) (you will see it in the lesson on quick sort). A hash table finds a key with one step on average, and with n if all keys land in one bucket (the module "Data structures"). There both cases are quoted, because both matter.

Try it

Predict the output

Six orders, three searches. How many checks does the program print?

ids = [1001, 1002, 1003, 1004, 1005, 1006]
for wanted in [1004, 1006, 1010]:
    checks = 0
    find_order(ids, wanted)
    print(checks)

Answer

3 / 5 / 6

4 / 6 / 0

4 / 6 / 6

Try it

Find the bug

Someone writes the search like this:

def find_order(ids, wanted):
    global checks
    found = -1
    for i in range(len(ids)):
        checks += 1
        if ids[i] == wanted:
            found = i
    return found

ids = [1001 + k for k in range(8)]
report(ids, 1001)
report(ids, 1005)
report(ids, 999)

1001: 0, checks: 8
1005: 4, checks: 8
999: -1, checks: 8

It finds the right index, but every search makes 8 checks. On which line is the bug?

Pick the line with the bug.

Exercise

New orders are searched for the most

Solve the task in your editor.

Searching from the end. Support almost always looks for orders from the last few days. Write find_latest, which searches from the end to the start and counts the checks, and run it in report for 1,000 orders with the numbers 2000 (the last one), 1001 (the first one) and 999 (not there):

2000: 999, checks: 1
1001: 0, checks: 1000
999: -1, checks: 1000

What is the best case now? And the worst? Has the class changed?

More tasks

The average from the end. Run the average case program with find_latest. Why is the average the same?
Wrong numbers. If half of the searches use a wrong number and the other half are uniform, how many checks are there on average with 1,000 orders?
Sorted by number. The orders are sorted by number. How can the search stop earlier when the number is not there? How many checks does it make for 999 then?

Test

Check yourself

1. Linear search finds the order with the first check. Does that make it O(1)?Yes, since it is one checkIt depends on the languageNo: that is the best case. The worst case is n checks, so it is O(n)

2. Why do we usually quote the worst case?Because it is the most common oneBecause it is a promise: whatever they search for, the work is not more than thisBecause it is the easiest to work out

3. Each of 1,000 orders is searched for equally often. How many checks does linear search make on average?1,0001About 500

4. Customers almost always look for their latest orders. How can you speed up the search without changing the algorithm?Nothing helpsSearch twiceSearch from the end to the start

Best, average and worst case

Cookies