In the previous two lessons we analyzed time and space "assuming the worst case", and several times we ran into functions that sometimes finish right away and sometimes traverse the whole input: has_duplicates bailed out on finding the first duplicate, all_before_b on finding the first late arrival. This lesson gives that observation a name and a method: the very same algorithm can have very different costs depending on which input it receives, not just on its size. We will learn to define and compute the best case, the worst case and the average case, to decide which one matters depending on the context (it is not the same for a mobile app as for a braking system), to relate them correctly to the O/Ω/Θ notations — debunking a widespread myth — and to understand intuitively amortized analysis, that "amortized O(1)" we left pending in the Python cost table of 02-01.

1. One algorithm, many inputs: the three cases
2. The three cases of find_stop
3. Which case matters? It depends on the context
4. Cases and notations: debunking the "O = worst case" myth
5. Amortized analysis: the case of list.append
6. An integrative example: validating the RutaBus schedules

Until now we wrote T(n) as if the size n determined the cost. But for many algorithms that is not so: two inputs of the same size can cost very differently. Searching for "Main Square" in a line with 40 stops costs 1 comparison if it is the first stop and 40 if it is the last one. The size is identical; the cost is not.

That is why the analysis splits into three questions, all three about inputs of size n:

• Best case: of all the inputs of size n, how much does the most favorable one cost? It is the algorithm's floor: it will never run faster.
• Worst case: how much does the most unfavorable input cost? It is the ceiling: an absolute guarantee, no matter what.
• Average case: if the inputs arrive according to a given distribution (typically "all equally likely"), how much does it cost on average? It is the realistic long-run expectation.

Three details of the definition that prevent confusion later:

1. The three cases refer to the input, not to the algorithm's luck: the best case of a search is not "having a fast computer", it is "the sought item being in the first position".
2. All three are functions of n: T_best(n), T_worst(n), T_average(n). The best case of searching among 40 stops and among 4,000 is "it is the first one", but it is still a (constant) function of the size.
3. The average case requires declaring a probability distribution over the inputs ("the sought stop can be at any position with equal probability"). If the assumed distribution does not resemble reality, neither does the computed average.

Let's apply this to the linear search from lesson 01-02, the one RutaBus uses to locate a stop within a line:

Basic operation: the comparison stop == name. Let n = len(line).

Best case — O(1). The most favorable input: name is in the first position. One comparison and a return. T_best(n) = 1, constant: Θ(1), whatever n is.

Worst case — O(n). The most unfavorable inputs: name is in the last position (n comparisons) or is not there (n comparisons and return -1). T_worst(n) = n: Θ(n). It is the guarantee we gave by default in 02-01.

Average case — O(n). Suppose the stop is on the line and each of the n positions is equally likely (probability 1/n each). If it is at position i (counting from 1), it costs i comparisons. The average cost is the mean of all the scenarios weighted by their probability:

The numerator is our old friend the arithmetic sum (02-01): n(n+1)/2. Dividing by n:

On average, the search walks through half the line. And asymptotically? n/2 is linear — constants are discarded (01-03) — so the average case is Θ(n), the same order as the worst case. It is a very instructive result: "twice as fast in practice" and "of the same order in theory" are compatible statements. And if failed searches were frequent (users misspelling the name), the real average would move even closer to n — remember: the average depends on the distribution you declare.

Summary:

The three analyses exist because they answer different needs. The right question is not "which is the good one?" but "what do I need to guarantee?":

Practical rules:

• The worst case is the default analysis (that is why we assumed it in 02-01): it is the only one that gives an unconditional guarantee, it is usually the easiest to compute, and it never errs on the side of optimism.
• The average case is the most informative when there is volume: a service handling a million searches a day cares about the average cost × a million, not about the single slowest search. Its weakness: it depends on an assumed distribution that may not hold.
• The best case, on its own, is almost propaganda: "my algorithm can finish in O(1)" commits to nothing (so can find_stop!). It is only valuable when you know the favorable inputs are the frequent ones in your system.

The celebrated example of this tension is quicksort (we will study it in 04-04): an excellent O(n log n) average that makes it dominate in practice, and an O(n²) worst case that demands precautions. A good part of algorithm engineering consists of managing that gap between average and worst case.

There is a false simplification circulating on the internet (and in some old training material — including a previous version of this course):

❌ "Big-O describes the worst case, Ω the best case and Θ the average case."

No. They are two independent axes that combine:

• The cases (best / worst / average) choose which cost function we are measuring: T_best(n), T_worst(n) or T_average(n). They talk about inputs.
• The notations (O / Ω / Θ, lesson 01-03) describe how a function grows: upper bound, lower bound or tight bound. They talk about functions, whichever they are.

Any notation can be applied to any case. All of these statements about find_stop are correct and mean different things:

Where does the confusion come from? From a legitimate colloquial usage: since T_best(n) ≤ T(n) ≤ T_worst(n) for every input, saying "the algorithm is O(n)" plain and simple usually means "not even its worst case exceeds linear", and "it is Ω(1)" usually refers to its best case being constant. The shortcut is convenient, but it merges the two axes and ends up producing the myth. Two practical consequences of keeping it straight:

• The most informative statement is Θ applied to a specific case: "worst case Θ(n), best case Θ(1)" says more than any loose O.
• Statements like "linear search is O(n²)" are technically true (a loose upper bound is still an upper bound, as we saw in 01-03) but useless. If someone gives you only an O, ask yourself: which case is it about, and is it a tight bound?

In the cost table of 02-01 we wrote that some_list.append(x) is "amortized O(1)", and we promised to explain it here. Amortized analysis is a fourth perspective, different from the previous three: it does not average over possible inputs, but over a sequence of operations actually executed, one after another.

The problem: a Python list stores its elements in a contiguous block of memory with a fixed capacity. As long as there is room left, append writes at the end: a genuine O(1). But when the block fills up, Python allocates a bigger one (roughly 12.5% larger, plus a margin) and copies all the elements: that particular append costs O(n).

So is append O(n)? Looking at one isolated operation in its worst case, yes. But that is a misleading answer, because the expensive operations cannot happen back to back: after each costly copy, the leftover capacity guarantees many cheap appends before the next one. Honest bookkeeping looks at the whole sequence:

• Inserting n elements starting from an empty list triggers resizes of geometrically growing sizes (each one a factor larger than the previous).
• The sum of all the copies of all the resizes is proportional to n — a geometric series behaves like its last term, not like the arithmetic sum of 02-01.
• Total cost: n cheap appends + O(n) of accumulated copies = O(n). Spread across the n operations: O(1) per operation.

That is what "amortized O(1)" means: a guarantee on the total of the sequence — n appends cost O(n), for sure, with no probabilistic assumptions — even though some individual operation may be expensive. An accounting metaphor: each cheap append "pays" a small surcharge that is saved up to finance the future copy; when the copy arrives, the fund covers it.

How it differs from the average case, which is what it is most often confused with:

A practical warning: "amortized" guarantees the total, not each individual operation. In the real-time arrivals example, an occasional slow append is invisible; in a strict real-time system (table in section 3), that isolated spike can be unacceptable even if the mean is perfect — once again, knowing what each analysis guarantees is what allows you to choose well.

Let's close the module by putting it all together. The RutaBus operations team loads the next day's schedule file every night: a table where each row is (line, stop, time). Before publishing it, it must be validated: no time may be malformed.

The full analysis, with n = number of rows:

• Best case — Θ(1): the very first row is already invalid (for example ("L1", "Main Square", "25:70")). One check and out. Note the irony: the algorithm's best case is the operator's worst day.
• Worst case — Θ(n): the file is completely valid — it must be examined in full to be able to guarantee it — or the only error is in the last row. And this is the case that matters here: the nightly process must have a sufficient time slot reserved every night, and the normal nights (a correct file) are precisely the ones with maximum cost.
• Average case: it depends on the error distribution. If rows are valid with very high probability (the norm in production), the typical case ≈ the worst: Θ(n). If the file came riddled with early errors, the average would drop — but planning the nightly window on that hope would be bad engineering: for sizing, worst case.
• Space (02-02): reused scalar variables, no copies or structures: auxiliary O(1). A validator can afford to read and discard.
• And if the validator additionally accumulated the correct rows in an output list with append, that cost would be amortized O(1) per row: a guaranteed Θ(n) total.

A single ten-line algorithm and we have used the whole module: line-by-line analysis, cases, correctly applied notations, space and amortization.

• Repeating the myth "O = worst case, Ω = best case": the cases choose the function to measure; the notations describe its growth. They combine freely: "best case O(1)" and "worst case Ω(n)" are perfectly well-formed statements.
• Confusing the best case with a small input: the best case is not "n = 1"; it is the most favorable input of size n. All three cases are functions of n.
• Giving an average case without declaring the distribution: "on average n/2" presupposes equally likely positions and that the element is there. Change the premise (many failed searches) and the average changes. Without an explicit distribution, an average asserts nothing.
• Selling the best case: "it can get down to O(1)" is true of almost any search with an early exit and guarantees nothing. Be suspicious of any analysis that only mentions the favorable scenario.
• Reading "amortized" as "always": amortized O(1) promises the total of the sequence, not each operation; some may be O(n). Irrelevant in an app, decisive in real time.
• Tip: when analyzing an algorithm with early exits (return inside the loop), systematically ask yourself three things: which input makes me exit on the first try? (best case), which one forces me to reach the end? (worst case), how do inputs arrive in my system? (the case I should optimize for).

Exercise 1. RutaBus checks whether two users can share a trip by verifying whether their lines have some stop in common, with the O(n²) version from 02-01:

Assuming len(line_a) = len(line_b) = n, describe the best-case input and the worst-case input, and give the order of each.

Exercise 2. Classify each statement as true or false, justifying it with the two axes (cases vs notations): a) "The best case of find_stop is O(n)." b) "The worst case of find_stop is Ω(n)." c) "find_stop is Θ(n) for every input." d) "The average case of find_stop is O(n²)."

Exercise 3. A stop's board keeps the arrivals in a list sorted by time, inserting each new arrival in its place:

Using the cost table from 02-01: (a) give the best and worst case of record_arrival and the input that triggers each; (b) reason whether insert can boast of being "amortized O(1)" like append, or not, and why.

Solution 1. Best case Θ(n) — careful, not Θ(1): the most favorable input is that the first stop of line_a is in line_b... but finding it with in can cost up to n comparisons; the rigorously optimal case is that it is additionally the first one of line_b: 1 comparison, Θ(1). This exercise teaches you to define the best case precisely: the optimal input is "first of A matches first of B" → Θ(1); "first of A is in B (anywhere)" can already cost Θ(n). Worst case Θ(n²): they share no stop at all — the n passes of the outer loop pay n comparisons each, with no early exit possible. Note that the worst case is precisely the answer "False", just as in schedule_is_valid the worst case was the valid file: verifying absence forces you to look at everything.

Solution 2. a) True. The best case is Θ(1), and every Θ(1) function is also O(n): a loose upper bound is valid (though uninformative). The statement is correct; useful, it is not. b) True. The worst case costs exactly n comparisons, so it is bounded from below by something linear: Ω(n). And it is also O(n); that is why the tight statement is Θ(n). c) False. For the input with the stop in the first position the cost is 1, which is not Θ(n). Precisely because the cases differ, the algorithm as a whole has no single Θ — you have to give one to each case. d) True but useless. The average is Θ(n) and therefore also O(n²): a true, loose upper bound. It is the canonical example of why "it is O(something)" on its own can be an empty piece of information.

Solution 3. (a) The bisect search costs O(log n) always. The variable cost is in insert: it shifts all the elements after the position. Best case: the arrival is the latest one and goes at the end — 0 shifts — → Θ(log n) total. Worst case: the arrival is the earliest one and goes at the front — n shifts → Θ(n) total. (b) No: the amortization of append works because the expensive operations (resizing) are necessarily scarce and the cheap ones prepay them. With insert no such mechanism exists: every insertion at the front costs O(n) every time, and an adversarial sequence (arrivals in reverse order, from latest to earliest... or an attacker, table in section 3) makes all the operations expensive: n insertions → arithmetic sum → Θ(n²) total, that is, Θ(n) per operation even in amortized terms. "Amortized" is not a magic spell: you must prove that the expensive operations cannot repeat.

With this lesson we complete the algorithm analysis arsenal. We have learned that the cost depends not only on the size of the input but on the input itself, and to measure it with three different yardsticks on find_stop: best case Θ(1), worst case Θ(n) and average case ≈ n/2 → Θ(n); we have seen that choosing the case is an engineering decision — worst case for guarantees, real time and hostile inputs; average for typical performance at volume; best case only when the favorable is the frequent —; we have debunked the myth "O = worst case, Ω = best case" by separating the two axes (the cases choose which function to measure, the notations describe how it grows); we have added amortized analysis with list.append — a guarantee on the whole sequence, with no probabilities —; and we have put it all together by validating RutaBus's nightly schedules, where the worst case (the correct file) turns out to be the normal day. Together with the line-by-line time analysis (02-01) and the space analysis (02-02), we can now answer with rigor the question "how much does this algorithm cost?" in all its variants.

But knowing how to measure algorithms is not the same as knowing how to create them. So far we have analyzed solutions already written; the natural next question is: faced with a new RutaBus problem — planning the optimal trip between two stops, assigning buses to lines, fitting schedules together —, how do you design a good algorithm from scratch? In Module 3 we will study the four great design strategies that already peeked out in 01-02: divide and conquer (03-01), greedy algorithms (03-02), dynamic programming (03-03) — where we will meet again, under its proper name, the idea of spending memory to avoid repeating work that we noted in 02-02 — and backtracking (03-04). And every design we produce will be put on trial with the tools this module has given us.