Best case, worst case, and space
In lesson 1-1 both step counts came from one specific input. But the same algorithm can be fast on one input and slow on another.
- Best case: the friendliest input. For a left-to-right scan, the target sits at index 0.
- Worst case: the cruelest input. The target is 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. Interviewers almost always want worst-case analysis, and they expect you to name the input that causes it.
Code exercise · python
Run this. The same function does 1 comparison, then 8, then 8, depending only on the input.
Quiz
A function scans a list and returns early when it finds the answer. Which input produces its worst case?
Space vs time
Steps are not the only cost. Space complexity counts the extra memory your algorithm allocates beyond the input.
Look back at lesson 1-1: dup_slow used O(1) space (just two loop counters) but O(n²) time. dup_fast used O(n) space (the seen set can grow to hold every item) to get O(n) time.
That is the classic trade: spend memory to save time. It is usually worth it, and saying the trade out loud ("I can do O(n) time if I may use O(n) extra space") is an interview habit worth building now.
Code exercise · python
Your turn. Write first_repeat(nums): return the first value that appears a second time while scanning left to right, or None if there is no repeat. Use a set for a single O(n) pass.
Quiz
first_repeat uses a set that can grow as large as the input. What is its time and space complexity?
Problem
You run first_repeat on a 300-item list whose values are all distinct. How many items does the scan visit before it gives up? Enter the number.