Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Best, Worst and Average Case

Editorial

Same code, different inputs

Search a list of 1,000 values for one of them, checking each in turn. If it's the first value, one comparison finds it. If it's the last, or isn't there at all, it takes 1,000. Same code, same n, and the cost runs from 1 to 1,000 depending on the input.

So "how fast is it?" needs a second question: on which input? There are three usual answers:

  • the best case: the input that makes it do the least work;
  • the worst case: the input that makes it do the most;
  • the average case: the work on a typical input, averaged over all the inputs it might get.

This lesson measures all three for a search and two sorts, shows the input that turns a fast sort into a slow one, the difference between an average and a randomized algorithm's expected time, and why a hash map is O(1) only on average.

Three dashed bands, each a row of eight tiles numbered 1 to 8. Best case: the target is first: tile 1 is green and ringed, the rest pale, and a pill reads 1 comparison. Average: each target in turn: eight orange tiles with the comparisons each one costs under it, 1 to 8, and a pill reads 4.5 on average. Worst case: the target is missing: eight grey tiles, all checked, a note reading target 9: not found, and a pill reads 8 comparisons. Focal line: same code, same n: the input decides the cost. Title: one search, three costs.

One search, three costs

The search counts its comparisons, for the first value, the last, a missing one, and every target in turn:

#include <bits/stdc++.h>
using namespace std;

pair<int, int> linearSearch(const vector<int>& nums, int target) {   // {index, comparisons}
    int comparisons = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        comparisons++;
        if (nums[i] == target) return {i, comparisons};
    }
    return {-1, comparisons};
}

int main() {
    vector<int> nums(1000);
    iota(nums.begin(), nums.end(), 1);                        // 1, 2, ..., 1000
    pair<int, const char*> targets[] = {{1, "first"}, {1000, "last"}, {0, "missing"}};
    for (auto [target, where] : targets) {
        auto [index, comparisons] = linearSearch(nums, target);
        printf("%s: index %d, comparisons %d\n", where, index, comparisons);
    }
    long long total = 0;
    for (int t : nums) total += linearSearch(nums, t).second;
    printf("every target in turn: %.1f comparisons on average\n", (double)total / nums.size());
}

// first: index 0, comparisons 1
// last: index 999, comparisons 1000
// missing: index -1, comparisons 1000
// every target in turn: 500.5 comparisons on average
def linear_search(nums, target):      # returns (index, comparisons)
    comparisons = 0
    for i in range(len(nums)):
        comparisons += 1
        if nums[i] == target:
            return i, comparisons
    return -1, comparisons


nums = list(range(1, 1001))           # 1, 2, ..., 1000
for target, where in ((1, "first"), (1000, "last"), (0, "missing")):
    index, comparisons = linear_search(nums, target)
    print(f"{where}: index {index}, comparisons {comparisons}")
average = sum(linear_search(nums, t)[1] for t in nums) / len(nums)
print(f"every target in turn: {average:.1f} comparisons on average")

# first: index 0, comparisons 1
# last: index 999, comparisons 1000
# missing: index -1, comparisons 1000
# every target in turn: 500.5 comparisons on average
public class Main {
    static int[] linearSearch(int[] nums, int target) {     // {index, comparisons}
        int comparisons = 0;
        for (int i = 0; i < nums.length; i++) {
            comparisons++;
            if (nums[i] == target) return new int[]{i, comparisons};
        }
        return new int[]{-1, comparisons};
    }

    public static void main(String[] args) {
        int[] nums = new int[1000];
        for (int i = 0; i < 1000; i++) nums[i] = i + 1;     // 1, 2, ..., 1000
        int[] targets = {1, 1000, 0};
        String[] where = {"first", "last", "missing"};
        for (int k = 0; k < 3; k++) {
            int[] r = linearSearch(nums, targets[k]);
            System.out.printf("%s: index %d, comparisons %d%n", where[k], r[0], r[1]);
        }
        long total = 0;
        for (int t : nums) total += linearSearch(nums, t)[1];
        System.out.printf("every target in turn: %.1f comparisons on average%n", (double) total / nums.length);
    }
}

// first: index 0, comparisons 1
// last: index 999, comparisons 1000
// missing: index -1, comparisons 1000
// every target in turn: 500.5 comparisons on average
function linearSearch(nums, target) {     // [index, comparisons]
    let comparisons = 0;
    for (let i = 0; i < nums.length; i++) {
        comparisons++;
        if (nums[i] === target) return [i, comparisons];
    }
    return [-1, comparisons];
}

const nums = Array.from({ length: 1000 }, (_, i) => i + 1);   // 1, 2, ..., 1000
for (const [target, where] of [[1, "first"], [1000, "last"], [0, "missing"]]) {
    const [index, comparisons] = linearSearch(nums, target);
    console.log(`${where}: index ${index}, comparisons ${comparisons}`);
}
const total = nums.reduce((sum, t) => sum + linearSearch(nums, t)[1], 0);
console.log(`every target in turn: ${(total / nums.length).toFixed(1)} comparisons on average`);

// first: index 0, comparisons 1
// last: index 999, comparisons 1000
// missing: index -1, comparisons 1000
// every target in turn: 500.5 comparisons on average

The best case is 1 comparison, the worst is n (a missing target costs as much as the last one), and the average over every target is (n + 1)/2, 500.5 here.

The case is not the bound. Best, worst and average pick which input you are talking about. Big O (and Θ and Ω, from Big O Notation) describe how that case's cost grows. So linear search is Θ(1) in its best case and Θ(n) in its worst; its average, (n + 1)/2, is Θ(n) too, because the ½ is a constant. "Big O is the worst case and Ω the best" is a common mix-up: every case has its own growth, and you can bound any of them from above or below.

The same shuffle in every language

Averages need random inputs, and each language's random numbers differ. So every program below makes its random orders with this one generator, and all four print the same counts:

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums
static int seed = (int) 2463534242L;

static int randomBelow(int bound) {          // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return Integer.remainderUnsigned(seed, bound);
}

static int[] shuffled(int n) {               // 0 .. n-1 in a random order
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) nums[i] = i;
    for (int i = n - 1; i > 0; i--) {
        int j = randomBelow(i + 1), t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    return nums;
}
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

shuffled(10) gave 8 1 6 4 2 9 3 0 7 5 in all four.

Insertion sort: sorted, reversed, shuffled

Insertion sort takes each value in turn and walks it left past every bigger value. How far each one walks depends on the order it started in:

long long insertionSort(vector<int> nums) {   // sorts a copy; returns how many comparisons it made
    long long comparisons = 0;
    for (int i = 1; i < (int)nums.size(); i++) {
        int key = nums[i], j = i - 1;
        while (j >= 0) {
            comparisons++;
            if (nums[j] <= key) break;                // in place: stop
            nums[j + 1] = nums[j];                    // bigger: move it right
            j--;
        }
        nums[j + 1] = key;
    }
    return comparisons;
}

int main() {
    int n = 1000;
    vector<int> sorted(n), reversed(n);
    iota(sorted.begin(), sorted.end(), 0);
    reverse_copy(sorted.begin(), sorted.end(), reversed.begin());
    printf("sorted: %lld\n", insertionSort(sorted));
    printf("reversed: %lld\n", insertionSort(reversed));
    long long fewest = LLONG_MAX, most = 0, total = 0;
    for (int run = 0; run < 25; run++) {
        long long c = insertionSort(shuffled(n));
        fewest = min(fewest, c), most = max(most, c), total += c;
    }
    printf("shuffled, 25 runs: fewest %lld, average %.1f, most %lld\n", fewest, total / 25.0, most);
}

// sorted: 999
// reversed: 499500
// shuffled, 25 runs: fewest 242735, average 251542.3, most 261782
def insertion_sort(nums):             # sorts nums; returns how many comparisons it made
    comparisons = 0
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if nums[j] <= key:        # in place: stop
                break
            nums[j + 1] = nums[j]     # bigger: move it right
            j -= 1
        nums[j + 1] = key
    return comparisons


n = 1000
print("sorted:", insertion_sort(list(range(n))))
print("reversed:", insertion_sort(list(range(n - 1, -1, -1))))
runs = [insertion_sort(shuffled(n)) for _ in range(25)]
print(f"shuffled, 25 runs: fewest {min(runs)}, average {sum(runs) / 25:.1f}, most {max(runs)}")

# sorted: 999
# reversed: 499500
# shuffled, 25 runs: fewest 242735, average 251542.3, most 261782
static long insertionSort(int[] nums) {      // sorts nums; returns how many comparisons it made
    long comparisons = 0;
    for (int i = 1; i < nums.length; i++) {
        int key = nums[i], j = i - 1;
        while (j >= 0) {
            comparisons++;
            if (nums[j] <= key) break;               // in place: stop
            nums[j + 1] = nums[j];                   // bigger: move it right
            j--;
        }
        nums[j + 1] = key;
    }
    return comparisons;
}

public static void main(String[] args) {
    int n = 1000;
    int[] sorted = new int[n], reversed = new int[n];
    for (int i = 0; i < n; i++) {
        sorted[i] = i;
        reversed[i] = n - 1 - i;
    }
    System.out.println("sorted: " + insertionSort(sorted));
    System.out.println("reversed: " + insertionSort(reversed));
    long fewest = Long.MAX_VALUE, most = 0, total = 0;
    for (int run = 0; run < 25; run++) {
        long c = insertionSort(shuffled(n));
        fewest = Math.min(fewest, c);
        most = Math.max(most, c);
        total += c;
    }
    System.out.printf("shuffled, 25 runs: fewest %d, average %.1f, most %d%n", fewest, total / 25.0, most);
}

// sorted: 999
// reversed: 499500
// shuffled, 25 runs: fewest 242735, average 251542.3, most 261782
function insertionSort(nums) {           // sorts nums; returns how many comparisons it made
    let comparisons = 0;
    for (let i = 1; i < nums.length; i++) {
        const key = nums[i];
        let j = i - 1;
        while (j >= 0) {
            comparisons++;
            if (nums[j] <= key) break;        // in place: stop
            nums[j + 1] = nums[j];            // bigger: move it right
            j--;
        }
        nums[j + 1] = key;
    }
    return comparisons;
}

const n = 1000;
console.log("sorted:", insertionSort(Array.from({ length: n }, (_, i) => i)));
console.log("reversed:", insertionSort(Array.from({ length: n }, (_, i) => n - 1 - i)));
const runs = Array.from({ length: 25 }, () => insertionSort(shuffled(n)));
const average = runs.reduce((a, b) => a + b, 0) / 25;
console.log(`shuffled, 25 runs: fewest ${Math.min(...runs)}, average ${average.toFixed(1)}, most ${Math.max(...runs)}`);

// sorted: 999
// reversed: 499500
// shuffled, 25 runs: fewest 242735, average 251542.3, most 261782
  • Sorted is its best case: each value compares once with its left neighbour and stays, 999 comparisons, O(n).
  • Reversed is its worst: each value walks all the way to the front, 1 + 2 + … + 999 = 499,500 comparisons, O(n²).
  • Shuffled lands near n²/4: 242,735 to 261,782 over 25 orders, 251,542.3 on average. Still O(n²): a quarter of the square grows like the square.

So insertion sort is O(n) on sorted input and O(n²) on most others. That's why it suits data that is nearly sorted already, and why library sorts use it on short runs (Big O Notation measured where it wins).

Quick sort's worst input is a sorted one

Quick sort picks a pivot, moves the smaller values to its left and the bigger ones to its right, and sorts each side the same way. Here the pivot is the last value of the range, and the count includes how many calls deep the sort goes; then the same sort with a random pivot:

int partition(vector<int>& nums, int lo, int hi, bool randomPivot) {
    if (randomPivot) swap(nums[lo + randomBelow(hi - lo + 1)], nums[hi]);   // a random value takes the pivot's place
    int pivot = nums[hi], i = lo;
    for (int j = lo; j < hi; j++)                // hi - lo comparisons
        if (nums[j] < pivot) swap(nums[i++], nums[j]);
    swap(nums[i], nums[hi]);
    return i;
}

// sorts nums[lo..hi]; returns {comparisons, how many calls deep it went}
pair<long long, int> quickSort(vector<int>& nums, int lo, int hi, bool randomPivot, int depth = 1) {
    if (lo >= hi) return {0, depth};
    int p = partition(nums, lo, hi, randomPivot);
    auto left = quickSort(nums, lo, p - 1, randomPivot, depth + 1);
    auto right = quickSort(nums, p + 1, hi, randomPivot, depth + 1);
    return {hi - lo + left.first + right.first, max(left.second, right.second)};
}

int main() {
    int n = 500;
    for (bool randomPivot : {false, true}) {
        vector<int> sorted(n);
        iota(sorted.begin(), sorted.end(), 0);
        vector<int> mixed = shuffled(n);
        pair<const char*, vector<int>*> inputs[] = {{"sorted", &sorted}, {"shuffled", &mixed}};
        for (auto [name, nums] : inputs) {
            auto [comparisons, deepest] = quickSort(*nums, 0, n - 1, randomPivot);
            printf("%s, %s: %lld comparisons, %d calls deep\n",
                   randomPivot ? "random pivot" : "last value as pivot", name, comparisons, deepest);
        }
    }
}

// last value as pivot, sorted: 124750 comparisons, 500 calls deep
// last value as pivot, shuffled: 4578 comparisons, 18 calls deep
// random pivot, sorted: 5560 comparisons, 21 calls deep
// random pivot, shuffled: 4552 comparisons, 17 calls deep
def partition(nums, lo, hi, random_pivot):
    if random_pivot:                  # a random value takes the pivot's place
        r = lo + random_below(hi - lo + 1)
        nums[r], nums[hi] = nums[hi], nums[r]
    pivot = nums[hi]
    i = lo
    for j in range(lo, hi):           # hi - lo comparisons
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[hi] = nums[hi], nums[i]
    return i


def quick_sort(nums, lo, hi, random_pivot, depth=1):
    """sorts nums[lo..hi]; returns (comparisons, how many calls deep it went)"""
    if lo >= hi:
        return 0, depth
    p = partition(nums, lo, hi, random_pivot)
    left = quick_sort(nums, lo, p - 1, random_pivot, depth + 1)
    right = quick_sort(nums, p + 1, hi, random_pivot, depth + 1)
    return hi - lo + left[0] + right[0], max(left[1], right[1])


n = 500
for random_pivot in (False, True):
    inputs = (("sorted", list(range(n))), ("shuffled", shuffled(n)))
    for name, nums in inputs:
        comparisons, deepest = quick_sort(nums, 0, n - 1, random_pivot)
        pivot = "random pivot" if random_pivot else "last value as pivot"
        print(f"{pivot}, {name}: {comparisons} comparisons, {deepest} calls deep")

# last value as pivot, sorted: 124750 comparisons, 500 calls deep
# last value as pivot, shuffled: 4578 comparisons, 18 calls deep
# random pivot, sorted: 5560 comparisons, 21 calls deep
# random pivot, shuffled: 4552 comparisons, 17 calls deep
static int partition(int[] nums, int lo, int hi, boolean randomPivot) {
    if (randomPivot) swap(nums, lo + randomBelow(hi - lo + 1), hi);   // a random value takes the pivot's place
    int pivot = nums[hi], i = lo;
    for (int j = lo; j < hi; j++)                // hi - lo comparisons
        if (nums[j] < pivot) swap(nums, i++, j);
    swap(nums, i, hi);
    return i;
}

static void swap(int[] nums, int a, int b) {
    int t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
}

// sorts nums[lo..hi]; returns {comparisons, how many calls deep it went}
static long[] quickSort(int[] nums, int lo, int hi, boolean randomPivot, int depth) {
    if (lo >= hi) return new long[]{0, depth};
    int p = partition(nums, lo, hi, randomPivot);
    long[] left = quickSort(nums, lo, p - 1, randomPivot, depth + 1);
    long[] right = quickSort(nums, p + 1, hi, randomPivot, depth + 1);
    return new long[]{hi - lo + left[0] + right[0], Math.max(left[1], right[1])};
}

public static void main(String[] args) {
    int n = 500;
    for (boolean randomPivot : new boolean[]{false, true}) {
        int[] sorted = new int[n];
        for (int i = 0; i < n; i++) sorted[i] = i;
        int[] mixed = shuffled(n);
        String[] names = {"sorted", "shuffled"};
        int[][] inputs = {sorted, mixed};
        for (int k = 0; k < 2; k++) {
            long[] r = quickSort(inputs[k], 0, n - 1, randomPivot, 1);
            System.out.printf("%s, %s: %d comparisons, %d calls deep%n",
                randomPivot ? "random pivot" : "last value as pivot", names[k], r[0], r[1]);
        }
    }
}

// last value as pivot, sorted: 124750 comparisons, 500 calls deep
// last value as pivot, shuffled: 4578 comparisons, 18 calls deep
// random pivot, sorted: 5560 comparisons, 21 calls deep
// random pivot, shuffled: 4552 comparisons, 17 calls deep
function partition(nums, lo, hi, randomPivot) {
    if (randomPivot) {                       // a random value takes the pivot's place
        const r = lo + randomBelow(hi - lo + 1);
        [nums[r], nums[hi]] = [nums[hi], nums[r]];
    }
    const pivot = nums[hi];
    let i = lo;
    for (let j = lo; j < hi; j++)            // hi - lo comparisons
        if (nums[j] < pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    [nums[i], nums[hi]] = [nums[hi], nums[i]];
    return i;
}

// sorts nums[lo..hi]; returns [comparisons, how many calls deep it went]
function quickSort(nums, lo, hi, randomPivot, depth = 1) {
    if (lo >= hi) return [0, depth];
    const p = partition(nums, lo, hi, randomPivot);
    const left = quickSort(nums, lo, p - 1, randomPivot, depth + 1);
    const right = quickSort(nums, p + 1, hi, randomPivot, depth + 1);
    return [hi - lo + left[0] + right[0], Math.max(left[1], right[1])];
}

const n = 500;
for (const randomPivot of [false, true]) {
    const inputs = [["sorted", Array.from({ length: n }, (_, i) => i)], ["shuffled", shuffled(n)]];
    for (const [name, nums] of inputs) {
        const [comparisons, deepest] = quickSort(nums, 0, n - 1, randomPivot);
        console.log(`${randomPivot ? "random pivot" : "last value as pivot"}, ${name}: ` +
                    `${comparisons} comparisons, ${deepest} calls deep`);
    }
}

// last value as pivot, sorted: 124750 comparisons, 500 calls deep
// last value as pivot, shuffled: 4578 comparisons, 18 calls deep
// random pivot, sorted: 5560 comparisons, 21 calls deep
// random pivot, shuffled: 4552 comparisons, 17 calls deep

On sorted input the last value is always the biggest, so every split leaves all the other values on one side and none on the other. The sort makes 499 + 498 + … + 1 = 124,750 comparisons and goes 500 calls deep, one level per value. On the shuffled order it made 4,578 comparisons and went 18 deep: the splits fall near the middle, so there are about log₂ n levels of n work each, O(n log n).

Two dashed panels of pivot trees, each node a pivot and its children the pivots of the two sides it split. Left, green, the order 3 7 1 2 5 6 8 4: 4 at the top, 2 and 7 below it, then 1, 3, 6 and 8, and 5 under 6, four levels, with a pill reading 13 comparisons, 4 levels. Right, red, 1 2 3 4 5 6 7 8 sorted: a chain running down a diagonal, 8, 7, 6 and on to 1, each pivot the biggest value left, with a pill reading 28 comparisons, 8 levels. Focal line: on sorted input every pivot is the biggest left. Title: sorted input makes every split lopsided.

Depth costs memory too: each level is a call waiting on the stack. On 1,000 sorted values Python's default limit of 1,000 calls stopped the sort with RecursionError: maximum recursion depth exceeded in comparison. In C++, 100,000 sorted values took 5.0 s, 4,999,950,000 comparisons and 100,000 calls deep, where the random pivot sorted the same input in 4 ms.

Average case and expected time

Quick sort with the last value as pivot is O(n log n) on average, over every order the input could come in, and O(n²) in the worst case. The trouble with an average over inputs is that it assumes the inputs come in at random, and real ones often don't: sorted and nearly sorted data is common, and someone who knows your pivot rule can hand you the worst order on purpose.

The random pivot moves the randomness into the algorithm. Now no input is bad: on sorted input it made 5,560 comparisons and went 21 deep, on the shuffled one 4,552 and 17. Its expected number of comparisons, averaged over its own coin flips, is 2(n + 1)Hₙ − 4n, about 4,806 for n = 500, and that holds for every input. An unlucky run can still be slow, but no input makes it likely.

  • Average case: averaged over inputs; it needs the inputs to be random.
  • Expected time: averaged over the algorithm's own random choices; it holds for any input.

Make It Slow. Arrange eight values to make each sort do as much work as you can, then as little. The counts come from running the sort on your order; the scale shows where your order sits among all 40,320 orders of eight values.

Make It Slow: find the order that makes each sort do the most work

Hash maps: O(1) on average

A hash map turns each key into a bucket number and keeps the key in that bucket. Look-ups and inserts are O(1) on average because the keys spread out over the buckets, a few per bucket. The worst case is every key in one bucket: then each insert compares against all the keys before it, O(n) per operation. In three of the four languages that input is easy to build:

#include <bits/stdc++.h>
using namespace std;

struct SeededHash {                     // the fix: mix each key with a seed picked when the program starts
    size_t operator()(long long x) const {
        static const unsigned long long seed = chrono::steady_clock::now().time_since_epoch().count();
        unsigned long long z = x + seed + 0x9e3779b97f4a7c15ULL;   // splitmix64
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
        z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
        return z ^ (z >> 31);
    }
};

template <class Map> double secondsToCount(const vector<long long>& keys) {
    auto start = chrono::steady_clock::now();
    Map counts;
    for (long long k : keys) counts[k]++;
    return chrono::duration<double>(chrono::steady_clock::now() - start).count();
}

int main() {
    const int n = 50000;
    mt19937_64 rng(1);
    vector<long long> randomKeys(n);
    for (auto& k : randomKeys) k = rng() % 1000000000000LL;
    unordered_map<long long, int> probe;
    for (long long k : randomKeys) probe[k]++;
    long long buckets = probe.bucket_count();          // the table's size once it holds n keys
    vector<long long> oneBucket(n);
    for (int i = 0; i < n; i++) oneBucket[i] = (i + 1) * buckets;   // every key lands in bucket 0
    printf("%d random keys: %.4fs\n", n, secondsToCount<unordered_map<long long, int>>(randomKeys));
    printf("%d multiples of %lld: %.4fs\n", n, buckets, secondsToCount<unordered_map<long long, int>>(oneBucket));
    printf("the same multiples, seeded hash: %.4fs\n",
           secondsToCount<unordered_map<long long, int, SeededHash>>(oneBucket));
}

// 50000 random keys: 0.0070s
// 50000 multiples of 85229: 3.2808s
// the same multiples, seeded hash: 0.0065s
import random
import time

P = 2 ** 61 - 1                       # Python hashes an int by its remainder after dividing by P


def seconds_to_count(keys):
    start = time.perf_counter()
    counts = {}
    for k in keys:
        counts[k] = counts.get(k, 0) + 1
    return time.perf_counter() - start


n = 10000
random_keys = [random.randrange(10 ** 12) for _ in range(n)]
same_hash = [(i + 1) * P for i in range(n)]    # every one hashes to 0
print("hash(P) =", hash(P), "and hash(7 * P) =", hash(7 * P))
print(f"{n} random keys: {seconds_to_count(random_keys):.4f}s")
print(f"{n} multiples of P: {seconds_to_count(same_hash):.4f}s")

# hash(P) = 0 and hash(7 * P) = 0
# 10000 random keys: 0.0018s
# 10000 multiples of P: 1.6897s
import java.util.*;

public class Main {
    static double secondsToCount(List<String> keys) {
        long start = System.nanoTime();
        Map<String, Integer> counts = new HashMap<>();
        for (String k : keys) counts.merge(k, 1, Integer::sum);
        return (System.nanoTime() - start) / 1e9;
    }

    public static void main(String[] args) {
        System.out.println("\"Aa\" and \"BB\" both hash to " + "Aa".hashCode() + " and " + "BB".hashCode());
        int blocks = 16, n = 1 << blocks;
        List<String> sameHash = new ArrayList<>(), randomKeys = new ArrayList<>();
        Random rng = new Random(1);
        for (int mask = 0; mask < n; mask++) {       // every mix of 16 "Aa" and "BB" blocks: one hashCode
            StringBuilder s = new StringBuilder(), r = new StringBuilder();
            for (int b = 0; b < blocks; b++) {
                s.append((mask >> b & 1) == 1 ? "Aa" : "BB");
                r.append((char) ('a' + rng.nextInt(26))).append((char) ('a' + rng.nextInt(26)));
            }
            sameHash.add(s.toString());
            randomKeys.add(r.toString());
        }
        secondsToCount(randomKeys);                  // warm up: Java compiles a method as it runs
        secondsToCount(sameHash);
        System.out.printf("%d random keys: %.4fs%n", n, secondsToCount(randomKeys));
        System.out.printf("%d keys with one hashCode: %.4fs%n", n, secondsToCount(sameHash));
    }
}

// "Aa" and "BB" both hash to 2112 and 2112
// 65536 random keys: 0.0167s
// 65536 keys with one hashCode: 0.1511s
  • C++: unordered_map puts an integer key in bucket key mod (bucket count). Every multiple of 85,229, its bucket count at 50,000 keys, goes into bucket 0, so counting 50,000 of them took 3.28 s, against 7 ms for random keys. A hash that mixes each key with a seed picked when the program starts put the same keys back to 6 ms. Programming contests use exactly these keys to break solutions, and the seeded hash is the usual defence.
  • Python: an integer's hash is its remainder after dividing by 2⁶¹ − 1, so every multiple of that number hashes to 0. 10,000 of them took 1.69 s, against 2 ms.
  • Java: "Aa" and "BB" have the same hashCode, so every string made of those blocks shares one. 65,536 of them took 0.15 s, against 17 ms: slower, but not by much, because Java's HashMap turns a bucket of 8 or more keys into a balanced tree (once the table has 64 buckets), so its worst is O(log n) per operation for keys it can compare, like strings.

The right answer in an interview is "O(1) on average, O(n) in the worst case".

Two dashed panels, each a table of 8 buckets numbered 0 to 7. Scattered keys, in green: 13, 22, 5, 30, 17, 41, 3 and 28 land at most two to a bucket, 17 and 41 in bucket 1, 13 and 5 in bucket 5, 22 and 30 in bucket 6. Multiples of 8, in red: 8, 16, 24 and on to 64 all land in bucket 0, a chain of eight, and the other buckets are empty. Below, a ticked card reads O(1) on average: a look-up checks 1 or 2 keys; a crossed card reads O(n) when every key collides: a look-up walks all n keys. Focal line: a hash map is only as fast as its keys spread. Title: every key in one bucket.

Which case to give

When an interviewer asks for the time complexity, give the worst case unless you say otherwise: it's the one you can promise. Say which case you mean whenever they differ:

  • A hash map: O(1) on average, O(n) in the worst case.
  • Quick sort: O(n log n) on average (expected, with a random pivot), O(n²) in the worst case.
  • Insertion sort: O(n²), and O(n) when the input is already sorted.
  • Binary search: O(log n); its best case, O(1), is the middle value, and nobody asks for it.

The best case is rarely worth saying: almost every search is O(1) when the first thing it looks at is the answer. A cost that is large once in a while but small on average over a run of operations, like a growing array's copy, has a fourth name, amortized; Amortized Analysis covers it.

Mistakes that cost an interview

"Quick sort is O(n log n)." On average. With a fixed pivot, sorted input makes it O(n²): 4,999,950,000 comparisons on 100,000 sorted values in C++, and RecursionError on 1,000 in Python. Say which pivot you mean, and pick a random one.

"A hash map is O(1)." On average. Say both cases, and know that keys can be chosen to collide: 3.28 s for 50,000 keys in C++.

Giving the best case as the answer. "Linear search is O(1) because the target might be first" answers a question nobody asked.

Mixing up the case and the bound. "O means worst case" is wrong: the worst case of linear search is Θ(n), its best case Θ(1), and either can be written with O.

Averaging over inputs you won't get. An average that assumes random input says nothing about sorted input, and real data is often sorted already.

Check yourself

Quiz

1 / 6

Multiple choice

This loop looks for a target that isn't in nums. How does its count grow with n?
long long count = 0;
for (int x : nums) {
    count++;
    if (x == target) break;
}

Practice

Complexity Quiz: Easy, Medium and Hard, at the end of this section, ask which case a question means as well as its growth. The cases come back in every section: binary search's worst case in Introduction to Binary Search, hash maps in Introduction to Hashing, and quick sort's pivot in the Sorting section. Next: Amortized Analysis, for a cost that is sometimes large but rare.