The whole topic rests on ONE idea: for inputs of the same size n So instead of one number, we describe cost with three honest answers — the luckiest input (best), the unluckiest (worst), and the typical one (average).
Before you can read the parent note comfortably, you need to own every symbol it throws at you. Below, each symbol appears in the order that lets the next one make sense. Nothing is used before it is built.
Think of an algorithm as a little machine. You feed it an input (a list, a number, a name to find). It does some steps and stops. We want to measure "how much work" — but work depends on what you feed in.
The picture shows two lists of the same length going into the same machine. One comes out after 1 step, the other after 8. Same size — different work. That single observation is why we need three cases. Hold onto it.
n n 1 , 2 , 3 , … how big the input is. For a list, n n
Picture a row of n short (n long (n for one fixed row length — we freeze n Why the topic needs it: cost naturally grows with size. If we didn't fix n big input or an unlucky one. Fixing n
Common mistake The number one confusion"Bigger n at a single n . You change the arrangement of the n the parent note for the full steel-man.
I I one specific filled-in input: not "a list of length 8" but "this exact list [3,7,1,9,2,8,4,6]". Two inputs can share the same size n I
If n I these specific contents". Change what's inside → new I n Why the topic needs it: best/worst/average are about comparing different I n . Without a name for "one particular input", we couldn't say "the least work over all inputs" precisely.
T ( I ) I T ( I ) how many basic operations the algorithm performs when you feed it the specific input I
T T ( I ) I Why we count only ONE kind of operation: a program does many little things per step, but they all grow together. Counting the dominant one (the comparison inside the loop) captures the growth without drowning in detail.
T ( I ) [9,4,7] looking for 7: we compare 9? (no), 4? (no), 7? (yes) → stop. So T ( I ) = 3 that input.
Now that we have a cost T ( I ) each input, we squeeze the whole pile of inputs of size n three summary numbers .
The figure lays out every size-n T ( I ) lowest dot (best), the highest dot (worst), and the balance point (average).
min ∣ I ∣ = n T ( I ) minimum value of T ( I ) all inputs I n |I| = n underneath means "only look at inputs of size n
Line up all the T min lowest dot. It answers: of every possible size-n That is the best case , written B ( n )
max ∣ I ∣ = n T ( I ) maximum of T ( I ) n highest one. That's the worst case , W ( n )
Worst case is a guarantee : no size-n W ( n )
∣ I ∣ = n I "the size of" . So ∣ I ∣ = n I n Why the topic needs it: it's the leash that keeps min max wrong size.
The average needs a new idea the min/max didn't: not all inputs are equally common. To average fairly, we must weight each input by how often it shows up.
Pr ( I ) I Pr ( I ) 0 1 how likely it is that the input you actually receive is exactly I Pr ( I ) n 1
Imagine a bag holding one ticket per possible input, but fatter inputs get more tickets . Pr ( I ) I n Pr ( I ) = n 1 Why the topic needs it: the average case is only meaningful once you decide how likely each input is . Change the assumed likelihoods → change the average. See Expected Value and Probability Distributions .
∑ ∑ repeated addition . ∑ i = 0 n − 1 ( stuff i ) i 0 n − 1 stuff , and total the results."
∑ total = 0; for i in range(...): total += stuff(i). The symbol under ∑
E [ T ( I ) ] probability-weighted average of the cost:
A ( n ) = E I [ T ( I ) ] = ∑ I Pr ( I ) T ( I ) I its cost by its probability , then add all those products.
The figure shows why weighting matters. Two inputs cost 2 10 6 toward the cheap side — nowhere near the midpoint. That is exactly why "average = (best + worst)/2" is wrong: rare expensive inputs barely tug the balance. This is the seed of the Quicksort average-case surprise.
Common mistake Why not just2 best + worst Pr ( I ) rare or common each input is. They only accidentally match when the distribution is symmetric.
The parent note keeps using one formula. Here's why that exact tool .
Why this tool and not another? In linear search and insertion sort, the cost of input number i proportional to i . Adding those costs up literally is 1 + 2 + …
The picture proof: stack bars of heights 1 , 2 , … , n second copy , flip it upside down, and slot it on top. Every column now has the same height n + 1 n n ( n + 1 ) 2 n ( n + 1 ) ÷ 2
Worked example Quick check,n = 4 1 + 2 + 3 + 4 = 10 2 4 ⋅ 5 = 10
Definition Growth notationΘ ( f ( n )) O ( f ( n )) Ω ( f ( n )) how fast a count grows as n O no faster than ", Ω at least as fast as ", Θ exactly like ".
Think of them as speed-limit signs on the count. They don't care whether T = 3 n T = 100 n Θ ( n ) n Why the topic needs it, and the key warning: these signs describe growth ; best/worst/average describe which input . They are two independent axes. You can say "best case is Θ ( n ) Θ ( n 2 ) Asymptotic Notation (Big-O, Omega, Theta) — that's your next stop after this page.
Growth words Theta O Omega
Cover the right side and answer aloud. If any stalls, re-read that section before the parent note.
What does n The input size ; it is held fixed — only the arrangement varies.
What is the difference between n I n big the input is; I specific filled-in input of that size.
What does T ( I ) A number — the count of basic operations the algorithm does on the exact input I
What do the bars in ∣ I ∣ = n "The size of I n
min ∣ I ∣ = n T ( I ) The best case B ( n ) n
max ∣ I ∣ = n T ( I ) The worst case W ( n )
What is Pr ( I ) The likelihood of receiving input I n 1
Write the average-case formula in words. Add up, over every input, its cost times its probability: ∑ I Pr ( I ) T ( I )
Why is average = ( best + worst ) /2 The midpoint ignores probabilities; rare expensive inputs barely shift the true weighted balance.
What does ∑ k = 1 n k 2 n ( n + 1 ) i
Are Θ/ O /Ω No — they measure growth rate ; best/worst/average measure which input . Independent axes.
