Skip to content
wannacode

Best, average and worst case

In short: The worst case is the most work an algorithm does on an input of size n; that is what we promise, while the average case is the expected work under an assumption about the input, usually that every input is equally likely.

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:

static long checks = 0;


static int findOrder(int[] ids, int wanted) {
    for (int i = 0; i < ids.length; i++) {
        checks++;
        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:

static void report(int[] ids, int wanted) {
    checks = 0;
    int at = findOrder(ids, wanted);
    String line = wanted + ": " + at;
    System.out.println(line + ", checks: " + checks);
}

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

int[] ids = new int[1000];
for (int k = 0; k < ids.length; k++) {
    ids[k] = 1001 + k;
}
report(ids, 1001);
report(ids, 1501);
report(ids, 999);
Output
1001: 0, checks: 1
1501: 500, checks: 501
999: -1, checks: 1000

See it

One search, three cases

static long checks = 0;


static int findOrder(int[] ids, int wanted) {
    for (int i = 0; i < ids.length; i++) {
        checks++;
        if (ids[i] == wanted) {
            return i;
        }
    }
    return -1;
}


static void report(int[] ids, int wanted) {
    checks = 0;
    int at = findOrder(ids, wanted);
    String line = wanted + ": " + at;
    System.out.println(line + ", checks: " + checks);
}


int[] ids = new int[8];
for (int k = 0; k < ids.length; k++) {
    ids[k] = 1001 + k;
}
report(ids, 1001);
report(ids, 1005);
report(ids, 999);
Step by step, in words
  1. 8 orders of the month, numbered 1001 to 1008 in the order they came in. The search goes from the start, one by one.
  2. The best case: the order is the first one. 1 check, and the search is over. Output: 1001: 0, checks: 1.
  3. The order is in the middle: 5 checks, n/2 + 1. Output: 1005: 4, checks: 5.
  4. The worst case: there is no such order. The search checks all 8 and only then returns -1. Output: 999: -1, checks: 8.
  5. 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).
  6. 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:

int[] ids = new int[1000];
for (int k = 0; k < ids.length; k++) {
    ids[k] = 1001 + k;
}
long total = 0;
for (int wanted : ids) {
    checks = 0;
    findOrder(ids, wanted);
    total += checks;
}
System.out.println("Total: " + total);
System.out.println("Average: " + (double) total / ids.length);
Output
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)
Algorithmn = 10n = 1,000n = 100,000
The order is the first one111
The order is in the middle650150,001
There is no such order101,000100,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. List.indexOf and List.contains walk the elements one by one: O(n) in the worst case. indexOf returns -1 if it 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?

int[] ids = {1001, 1002, 1003, 1004, 1005, 1006};
for (int wanted : new int[] {1004, 1006, 1010}) {
    checks = 0;
    findOrder(ids, wanted);
    System.out.println(checks);
}
Answer

Try it

Find the bug

Someone writes the search like this:

static int findOrder(int[] ids, int wanted) {
    int found = -1;
    for (int i = 0; i < ids.length; i++) {
        checks++;
        if (ids[i] == wanted) {
            found = i;
        }
    }
    return found;
}
int[] ids = new int[8];
for (int k = 0; k < ids.length; k++) {
    ids[k] = 1001 + k;
}
report(ids, 1001);
report(ids, 1005);
report(ids, 999);
Output
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 findLatest, 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):

Output
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 findLatest. 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)?
2. Why do we usually quote the worst case?
3. Each of 1,000 orders is searched for equally often. How many checks does linear search make on average?
4. Customers almost always look for their latest orders. How can you speed up the search without changing the algorithm?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·