Skip to interview prep
Apexed

62. Analyse these nested loops: (a) outer i from 1 to n, inner j from 1 to i; (b) outer i doubling up to n, inner j from 1 to i; (c) outer i from 1 to n, inner j doubling up to n.

MediumAlgorithm analysis

Technical
Show model answer

(a) The inner loop runs 1 + 2 + ... + n = n(n+1)/2 times: Θ(n²). (b) The inner loop runs i times for i = 1, 2, 4, ..., up to n, which is a geometric series summing to less than 2n: Θ(n). (c) Each of the n outer iterations does about log n inner iterations: Θ(n log n).

The general technique is to write the total work as a sum over the outer variable and evaluate it with known identities, rather than multiplying the bounds of the two loops. Multiplying would wrongly give n log n for case (b).

Analyse these nested loops: (a) outer i from 1 to n, inner j from 1 to i; (b) outer i doubling up to n, inner j from 1 to i; (c) outer i from 1 to n, inner j do