Best case, worst case, and space

Best case, worst case, and space

In lesson 1-1 both step counts came from one specific input. The same algorithm can be fast on one input and slow on another, so a single measurement is not yet an analysis.

• Best case is the friendliest input. For a left-to-right scan, that is the target sitting at index 0.
• Worst case is the cruelest input. That is the target sitting last, or missing entirely.

When people say linear search is O(n) they mean the worst case, because that is the promise you can rely on. A best case of O(1) is worth nothing if the data does not cooperate.

Interviewers almost always want worst-case analysis, and they expect you to name the input that causes it rather than just quoting the notation.

One function, three costs

The same search does 1 comparison, then 8, then 8, depending only on its input.

def linear_search(nums, target):
    comparisons = 0
    for i, n in enumerate(nums):
        comparisons += 1
        if n == target:
            return i, comparisons
    return -1, comparisons

nums = [7, 12, 3, 44, 9, 21, 5, 30]
print(linear_search(nums, 7))
print(linear_search(nums, 30))
print(linear_search(nums, 99))

Output

(0, 1)
(7, 8)
(-1, 8)

Nothing in the function changed between the three calls, so all of the variation comes from the data.

Searching for 7 is the best case, since it sits at index 0 and the loop returns after one comparison. Searching for 30 is the worst hit, at the last index and eight comparisons.

The miss also costs 8, which is the case worth dwelling on. A scan cannot report not found until it has ruled out every element, so a miss always costs the full n.

That is why the worst case is stated as a miss rather than as a late hit. Both cost n, but only the miss is guaranteed to.

The worst case comes from an input where the answer is missing, so the scan never returns early.

Worst case means the input that forces the most work, and an early return is exactly the thing an adversarial input needs to prevent. If the answer is absent, every check fails and the loop runs all n times.

A late hit costs the same n comparisons, which is why the last index is often given as the answer too. The difference is that a miss is the only case guaranteed to cost n, since a hit anywhere earlier costs less.

Saying the worst case is a miss, which costs n comparisons, is exactly the sentence an interviewer is listening for. Naming the input is what separates an analysis from a recited result.

Space against time

Steps are not the only cost. Space complexity counts the extra memory an algorithm allocates beyond the input it was given.

Look back at lesson 1-1. dup_slow used O(1) space, just two loop counters, and paid O(n²) time. dup_fast used O(n) space, since the seen set can grow to hold every item, and got O(n) time for it.

That is the classic trade, spending memory to save time, and it is usually worth taking. Memory is cheap and quadratic time is not.

It is not always available, though. A stream too large to hold in memory, or an embedded system with a fixed budget, forces the O(1)-space version even when it is slower.

Saying the trade out loud is an interview habit worth building now. Something like I can do O(n) time if I may use O(n) extra space tells the interviewer you know there are two axes rather than one.

first_repeat

The first value that appears a second time while scanning left to right, or None.

def first_repeat(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return n
        seen.add(n)
    return None

print(first_repeat([4, 8, 15, 8, 4]))
print(first_repeat([1, 2, 3]))

Output

8
None

This is dup_fast from lesson 1-1 with the return value changed. The structure is identical, one pass and one set, which is worth noticing because three different questions have now been answered by the same shape.

Membership is checked before the add, the same rule as before, since adding first would make every value look repeated.

The answer is 8 rather than 4, and the distinction is the word first. Both values repeat, but 8's second copy appears at index 3 while 4's appears at index 4, so returning on the first hit gets the earlier one automatically.

The second call returns None after a complete pass, which is the no-repeats case and also the worst case for this function.

It is O(n) time and O(n) space.

The time comes from one pass with O(1) average set operations per item, so n items cost about n units of work.

The space comes from the set, which may end up holding almost every element. On the all-distinct input it holds all n of them, and that is the case that sets the bound.

So this function traded space for time, the most common trade in the whole course. The nested-loop version used O(1) space and paid O(n²) time, and neither is universally correct.

Stating both numbers together is the habit to build. An algorithm described only by its time complexity is described only halfway.

It visits all 300 items.

With no repeats the early return never fires, so the loop runs to completion and every item is checked exactly once.

That makes the all-distinct input the worst case for this function, which is a slightly counterintuitive result. The input with nothing interesting in it is the one that costs the most.

Its space cost peaks there too. The seen set ends up holding all 300 values, since nothing was ever found early enough to stop the additions.

Being able to name the exact input that forces the worst case, rather than reciting O(n), is the skill interviewers probe. The notation is the conclusion, and the input is the argument for it.