Best, Worst, and Average Case

Two inputs of the same size can cost very different amounts. Searching a list for an id stops at the first match: if the id sits at index 0, that takes 1 comparison, the best case. A missing id gets compared with every item, the worst case. If the id is equally likely to sit anywhere, the search stops about halfway on average.

A single Big O quoted for an algorithm is usually the worst case, the bound the code can promise on every input. Hash lookups are the common exception: the O(1) quoted for a dict or set lookup is an average, and so is the O(n + m) of a join built on one. Best cases matter for a different reason: they explain how a job that ran in seconds on test data crawls on production data, whose inputs land on the slow path.

OperationBest caseAverage caseWorst case
x in some_listO(1): x is firstO(n): about n/2 readsO(n): x is missing
Halving search, sorted listO(1): x is in the middleO(log n)O(log n)
sorted()O(n): input already in orderO(n log n)O(n log n)
Pair check inside each groupO(n): every group has 1 rowdepends on group sizesO(n²): all rows in 1 group

Skew: when 1 key holds most of the rows

Pipelines often split work by key: per user, per country, per day. A linear per-key step costs the same however rows spread across keys. A per-key step that grows faster than linear does not: its total depends on the spread. Take a step that compares every pair of a user's events to catch near-duplicates, so a user with k events costs about k² checks. Here are 1,000,000 events spread 2 ways.

Both spreads average 1,000 rows per user, so the average hides the trouble. Skew is a worst case the data chooses for you: a bot account, a default value such as an empty string, or every row with a missing key landing in the same None group.

Measuring skew in a single pass

Counting rows per key takes 1 pass and a dict. Compare the largest count with the average: a ratio near 1 means an even spread, and a ratio in the hundreds means 1 key will own any per-key step that grows faster than linear.

events = ["u1", "u2", "bot", "u3", "bot", "bot",
          "u1", "bot", "bot", "u2", "bot", "bot"]

counts = {}
for user in events:
    counts[user] = counts.get(user, 0) + 1

average = len(events) / len(counts)
hottest = max(counts, key=counts.get)
print("rows per user:", counts)
print("average:", average)
print("hottest:", hottest, counts[hottest])

pair_checks = 0
for user in counts:
    pair_checks += counts[user] * counts[user]
print("pair checks:", pair_checks, "of which bot:", counts["bot"] ** 2)

Output:

rows per user: {'u1': 2, 'u2': 2, 'bot': 7, 'u3': 1}
average: 3.0
hottest: bot 7
pair checks: 58 of which bot: 49

The bot holds 7 of 12 rows and 49 of 58 pair checks. Common repairs: drop or cap known bot keys, send the hot key down its own cheaper path, or replace the per-key pair check with a sort that lines near-duplicates up next to each other.

is_new runs once for every incoming row. Which batch of incoming ids makes it do the most comparisons in total?

loaded_ids = [101, 102, 103, 104, 105, 106, 107, 108]

def is_new(record_id):
    return record_id not in loaded_ids

Guarding a quadratic step

A guard that decides whether a batch is safe for a per-key pair check has to look at the key that sets the cost. The average spreads the hot key's rows across every key and reports a typical size instead. Batch B below has 1 key with 900 rows and 99 keys with 1 row each. Its average is under 10 rows per key, yet it needs more than 8 times the pair checks of Batch A, where 10 keys hold 100 rows each. Because a key with k rows costs k² checks, the largest count decides the total, so the guard has to compare the largest key's count with the limit.

BatchKeysRowsAverage per keyLargest keyPair checks
A101,000100100100,000
B1009999.99900810,099

About this lesson

This section is part of the Complexity: Intermediate lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.