1
Choose one dominant operation
Comparisons for a search or sort, multiplications for arithmetic. Counting everything changes only the constant.
Lesson · Algorithms and Complexity · Analysis
Analysing Iterative Algorithms
Nested loops multiply, sequential blocks take the maximum, and a loop whose bound depends on the outer index gives a sum — which is Induction and Recursion's summation formulas doing the work.
sequential blocks add, so the class is the MAXIMUM
nested loops multiply the iteration counts
dependent inner bound gives a SUM — evaluate it
worst / average / best case are different functions
Three loop patterns
Core ideas
What this lesson establishes
Analysis of a loop is counting how many times the body runs, which is usually a sum Induction and Recursion already evaluated.
2
Nested loops multiply, sequences take the maximum
Two independent nested loops give the product; two blocks in sequence give the sum, which asymptotically is the larger.
3
A dependent inner bound gives a sum
for i = 1 to n: for j = 1 to i runs Σ i = n(n+1)/2 times, which is Θ(n²) — the formula of “Induction with Sums and Products”, in Induction and Recursion.
The material
Counting operations
The three patterns, the case distinction, and four worked analyses.
Sequential blocks
for i = 1 to n: … n operations
for j = 1 to n²: … n² operations
total n + n² = Θ(n²)
Adding the costs and taking the dominant term. This is the sum rule of “Big-O, Big-Omega and Big-Theta”, and it means a fast block before a slow one contributes nothing asymptotically.
Independent nested loops
for i = 1 to n:
for j = 1 to m:
constant work
total n · m and if m = n, Θ(n²)
Dependent nested loops
for i = 1 to n:
for j = 1 to i:
constant work
total Σ_{i=1}^{n} i = n(n+1)/2 = Θ(n²)
The constant differs from the independent case — half as many iterations — and the class does not. This is where the summation formulas of “Induction with Sums and Products”, in Induction and Recursion, earn their place, and where a triple dependent nest gives Σ i² = Θ(n³).
Loops that multiply or divide
i = 1
while i < n: i = i · 2
i takes the values 1, 2, 4, 8, …, so the loop runs ⌈log₂ n⌉ times.
for i = 1 to n:
j = 1
while j < n: j = j · 2
total n · log₂ n = Θ(n log n)
Any loop whose counter is multiplied or divided by a constant runs logarithmically many times. Recognising that pattern is what identifies the log factors in an analysis.
Worst, average and best case
Definition · The three cases
Worst case is the maximum cost over inputs of size n; best case the minimum; average case the expectation over some distribution of inputs.
linear search best 1 worst n average about n/2
insertion sort best n worst n²/2 average n²/4
quicksort best n log n worst n² average n log n
merge sort n log n n log n n log n
bubble sort n²/2 n²/2 n²/2 — data-independent
Two things stand out. Merge sort and bubble sort have identical bounds in all three cases, for opposite reasons — one is always efficient and the other always wasteful, and neither looks at the data to decide how much work to do. And quicksort's average and worst cases differ by a whole class, which is why the unqualified O(n log n) claim of “Big-O, Big-Omega and Big-Theta” is wrong.
The average case needs a distribution over inputs, and stating it is part of the claim. "Average case Θ(n log n)" for quicksort assumes all input orderings equally likely, which real data frequently violates — nearly sorted input is the classic bad case for a naive pivot.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Analysing a loop nest
Innermost outward.
1
Choose the operation to count
The one performed most often: comparisons, multiplications, array accesses. Others differ by a constant factor.
2
Count the innermost loop's iterations
As a function of the outer indices. This is where the dependence shows.
3
Work outward, summing or multiplying
Independent bounds multiply; a dependent bound gives a sum to evaluate with Induction and Recursion's formulas.
4
State which case you have analysed
Worst, best or average, and for the average say what distribution. An unqualified bound is ambiguous.
Iterative analysis
Score 0 / 0Choose the answer you can justify.
Three nests
Same shape, three different answers.
A. for i = 1 to n:
for j = 1 to n:
for k = 1 to n: op
independent nests: n · n · n = Θ(n³)
B. for i = 1 to n:
for j = i to n: op
inner runs n − i + 1 times
Σ_{i=1}^{n} (n − i + 1) = Σ_{m=1}^{n} m = n(n+1)/2 = Θ(n²)
C. for i = 1 to n:
j = n
while j > 1: j = j / 2; op
inner runs ⌊log₂ n⌋ times, independent of i
total Θ(n log n)
B is the one worth checking: reindexing the sum by m = n − i + 1 turns it into Σ m, which Induction and Recursion evaluated. Recognising that substitution is most of the technique for dependent nests.
Common mistakes
1
Multiplying loop bounds when the inner one depends on the outerThat over-counts by a factor of 2 for a triangular nest. Write the sum and evaluate it.
2
Adding nested loop costsNesting multiplies. Sequential blocks add, and the two are easy to confuse when reading quickly.
3
Not saying which caseInsertion sort is Θ(n) on sorted input and Θ(n²) on reversed input. An unqualified bound is ambiguous between them.
Check your understanding
✓
Finish when a triangular nest gives you a sum, not a product.
Analyse for i = 1 to n: for j = 1 to i: for k = 1 to j: op and get Σ_i Σ_j j, which is Θ(n³) with a constant of 1/6. The reindexing is the skill.
Note: Modern hardware complicates all of this: cache behaviour can make an algorithm with more operations run faster, because memory locality dominates. Operation counting remains the right first analysis and is not the last word.