Time complexity: loops and the master theorem, quick guide

Most time complexity questions in exams reduce to two skills: counting how many times a loop body runs, and solving a recurrence.

Loops

• A loop for (i = 1; i <= n; i++) runs n times, so O(n).
• A loop where i doubles each step (i = i * 2) runs about log2(n) times, so O(log n).
• Nested loops multiply, but only if the inner count does not depend on the outer variable in a way that changes the sum. For for i in 1..n with inner for j in 1..i, the total is n(n+1)/2, which is O(n^2).

Recurrences (master theorem) For T(n) = a T(n/b) + f(n), compare f(n) with n^(log_b a):

• If f(n) is smaller by a polynomial factor, T(n) = Theta(n^(log_b a)).
• If they are the same order, T(n) = Theta(n^(log_b a) log n).
• If f(n) is larger (and the regularity condition holds), T(n) = Theta(f(n)).

Example: T(n) = 2T(n/2) + n. Here n^(log_2 2) = n, same order as f(n), so T(n) = Theta(n log n), which is merge sort.

I solved 6 more loop and recurrence problems step by step on my blog TechVani (originally published there): https://techvaniai.blogspot.com/2026/10/time-complexity-questions-6-solved-loop.html