Search for key x in array a[0..n-1], scanning left to right, stop on first match.
for i in 0..n-1:
if a[i] == x: return i # success
return -1 # not found
Best case.Why this step? The cheapest arrangement makes the loop stop immediately — a[0] == x. One comparison.
B(n)=1∈Θ(1)
Worst case.Why this step? The most expensive case forces scanning everything: x is at the last slot, or absent. We do n comparisons.
W(n)=n∈Θ(n)
Average case (successful search, x equally likely at each position).Why this step? If x is at index i (prob n1), it costs i+1 comparisons. Take the expectation:
A(n)=∑i=0n−1n1(i+1)=n1∑k=1nk=n1⋅2n(n+1)=2n+1∈Θ(n)Why this step?∑k=1nk=2n(n+1) (Gauss pairing). So on average we scan about half the array.
for i in 1..n-1:
key = a[i]
j = i-1
while j>=0 and a[j] > key: # comparison + shift
a[j+1] = a[j]; j -= 1
a[j+1] = key
Best case — already sorted.Why this step? If the array is ascending, the while condition a[j] > key is false on the first test every time. Each of the n−1 outer iterations does exactly 1 comparison.
B(n)=n−1∈Θ(n)
Worst case — reverse sorted.Why this step? Each new key is smaller than everything before it, so the inner loop walks all the way to the front. Iteration i does i comparisons:
W(n)=∑i=1n−1i=2(n−1)n∈Θ(n2)
Average case (random permutation).Why this step? For element i, on average it sinks halfway into the sorted prefix, costing ≈i/2 comparisons:
A(n)≈∑i=1n−12i=21⋅2(n−1)n=4n(n−1)∈Θ(n2)
The minimum number of operations over all inputs of a fixed size n.
What does worst-case complexity measure?
The maximum operations over all inputs of fixed size n — the unluckiest arrangement.
Define average-case formally.
A(n)=∑IPr(I)T(I), the expected cost under an assumed input distribution.
In best/worst/average, what is held constant?
The input size n; only the input's arrangement/content varies.
Linear search: best, worst, average comparisons?
1, n, 2n+1 respectively.
Insertion sort best vs worst case order?
Best Θ(n) (already sorted), worst Θ(n2) (reverse sorted).
Why is "average = (best+worst)/2" wrong?
Average is probability-weighted; midpoint ignores how rare/common extreme inputs are (e.g. quicksort avg is Θ(nlogn), not midpoint with Θ(n2)).
Is Big-O the same as worst case?
No. O/Ω/Θ are bound types; best/worst/average are which input you consider — they're independent.
Sum formula used in these derivations?
∑k=1nk=2n(n+1).
Recall Explain it to a 12-year-old
You're looking for your friend in a line of kids. If she's right at the front, you find her instantly — that's the best case. If she's at the very back (or not in line!), you check everyone — that's the worst case. If you do this many times and average how many kids you check, it's usually about half the line — that's the average case. Same line length, but luck changes how long it takes!
Dekho, ek hi algorithm same size ke alag-alag inputs pe alag time le sakta hai. Isliye hum sirf "n elements me kitna time" nahi bolte — hum batate hain kaunse input pe. Yahin se aate hain teen cases: best (sabse lucky arrangement, sabse kam operations), worst (sabse unlucky, sabse zyada operations), aur average (typical random input pe expected operations). Important baat: teeno me n same rehta hai, sirf input ka arrangement badalta hai — yeh mat samajhna ki best matlab chhota n aur worst matlab bada n.
Linear search se samjho: agar element pehle slot pe mil gaya to 1 comparison (best). Agar last me ya hai hi nahi to poore n comparisons (worst). Random query pe average 2n+1, yaani lagbhag aadhi list. Insertion sort aur dramatic hai — already sorted array pe Θ(n) (best), reverse sorted pe Θ(n2) (worst). Isiliye nearly-sorted data ke liye insertion sort accha maana jaata hai.
Ek common galti: log sochte hain "average = (best + worst) ka aadha". Galat! Average ek probability-weighted mean hota hai, ∑Pr(I)T(I). Quicksort dekho — best aur average dono Θ(nlogn) hain, lekin worst Θ(n2), kyunki bure pivots kabhi-kabhi hi aate hain. Aur yaad rakho: Big-O, Omega, Theta sirf bound ke types hain; woh best/worst/average se alag cheez hain — dono ko mix mat karna.
