Time Complexity — loops

Most complexity questions in placement tests are really questions about loops. Learn to read a loop’s growth pattern and 80% of the marks are yours.

The core patterns

• for (i = 0; i < n; i++) — runs n times → O(n).
• Two independent nested loops over n → n × n iterations → O(n²).
• Dependent bound: for (i = 0; i < n; i++) for (j = 0; j <= i; j++) — inner loop runs 1 + 2 + … + n = n(n+1)/2 times → still O(n²), but exam options often bait you with O(n log n) here.
• Multiplicative update: for (i = 1; i < n; i = i * 2) — i doubles each pass, so the loop runs log₂ n times → O(log n). The same holds for i = i / 2.
• Combined: an O(n) loop containing an O(log n) loop → O(n log n) — the shape of heap sort and merge sort.

The method (works on any loop)

1. Write the number of iterations of each loop as a function of n.
2. Multiply counts for nested loops; add counts for sequential loops.
3. Keep the fastest-growing term and drop constant factors: 3n² + 5n + 7 is O(n²).

Traps to watch

• An early break/return changes the best case, not the worst case — read which case the question asks for.
• i = i * 2 starting from 0 never progresses — a definiteness trap.
• Loop bounds like i * i < n mean i runs to √n → O(√n).

Work the examples in the video by hand before checking — the counting habit is the skill.