Time and Space Complexity

The previous lesson treated each algorithm as if it had one cost. That was a simplification. Take the most basic search there is, linear search: walk the list from the front until you find the value. If the value sits in the first slot, you are done in one comparison. If it sits in the last slot, or is not there at all, you compare against every element. Same algorithm, same list size, wildly different work. The input's size was fixed, what changed was which input of that size you got.

Picture looking for your keys. Best case, they are in the first pocket you check. Worst case, they are in the last one, and you only know after emptying everything. Average case, somewhere in the middle drawer of experience. The searching procedure never changed, your luck did. Complexity analysis simply refuses to depend on luck, which is why the worst case gets top billing.

Three cases, one algorithm

• Best case: the most favorable input of size n. Linear search: the target is the first element, one comparison, O(1).
• Average case: the expected cost over typical or random inputs. Linear search for a target equally likely to be anywhere: about n/2 comparisons, which is O(n) once constants drop.
• Worst case: the least favorable input of size n. Linear search: the target is last or absent, n comparisons, O(n).

Worst case is the default claim in engineering, and for a serious reason: it is a guarantee. A worst-case bound holds for every input, including the one a hostile user crafts on purpose. Average case is honest only when you can defend the assumption about input distribution, and attackers exist precisely to violate such assumptions. Hash tables, coming three lessons from now, are the canonical study in this tension: excellent on average, degraded by adversarial keys, and engineered specifically to make the average case trustworthy.

Cases are not bounds

Here is the confusion that trips up half the internet: people say big-O means worst case. It does not. Big-O, Omega, and Theta are bounds you can place on any function. Best, average, and worst case are different functions describing the same algorithm under different inputs. You can perfectly well give a big-O of the best case, linear search's best case is O(1), or an Omega of the worst case. The sloppy phrase survives because the most common sentence anyone needs is an upper bound on the worst case, so big-O and worst case travel together in casual speech. Keep the two axes separate in your head, choose a case, then bound it, and you will read algorithm claims more precisely than most working programmers.

Space: the same lens, pointed at memory

Everything so far counted time. Memory is analyzed identically: how does the number of memory cells the algorithm needs grow with n? The useful measure is auxiliary space, the extra memory beyond the input itself. Summing a list in place needs one accumulator no matter how long the list is, O(1) auxiliary space. Building a reversed copy of a list needs a whole second list, O(n). And, foreshadowing the next lesson, a recursive function that goes n calls deep holds n stack frames alive at once, O(n) space that is easy to miss because no visible variable holds it.

Time and space trade against each other constantly, and you will meet the trade on both sides of protection work. Merge sort buys its guaranteed O(n log n) time with O(n) of scratch space, while selection sort sorts in place with O(1) extra but pays quadratic time. Memoization, in the recursion lesson, spends memory to collapse exponential time to linear. Obfuscated programs make the same deal in reverse: string tables, decoy data, and virtualization bytecode inflate a shipped file's size and memory footprint to raise the cost of reading it. None of these are free lunches, they are purchases, and complexity is the price tag on both currencies.

The adversarial reading

This Academy cares about worst-case thinking for a second reason: it is the security mindset in mathematical form. Average-case analysis asks what a random input costs; worst-case analysis asks what the most hostile possible input costs, which is precisely the question defenders must ask about attackers. When later levels weigh a protection technique, the question is never how it holds up against a casual reader, but what the cheapest reliable attack costs, the adversary's best case against your defense. The habit of asking who chooses the input, and what happens when they choose maliciously, transfers directly from this lesson to threat modeling.

Best, average, and worst case describe the same algorithm under lucky, typical, and hostile inputs of the same size. Worst case is the engineering default because it is a guarantee. Big-O is a bound, cases are scenarios, and the two axes are independent. Space is analyzed with the identical growth lens, counting auxiliary memory beyond the input.

Frequently asked questions