Nested loops often drive complexity. Count how many times the inner body runs: independent loops add; nested loops multiply.
Patterns
- Single loop 0..n-1 → O(n)
- Two nested 0..n-1 → O(n²)
- Outer n, inner halving j → O(n log n)
- Loop i=0..n, inner j=0..i → still O(n²) (triangular)
Triangular inner loop
#include
int main() {
int n = 100;
long long ops = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
++ops;
std::cout << "ops ~ n(n-1)/2 = " << ops << "\n";
return 0;
} Halving pattern
While n > 0; n /= 2 runs O(log n) iterations—foundation for binary search and heap height analysis.
Important interview questions and answers
- Q: i and j both to n?
A: O(n²)—classic interview trap. - Q: j only to i?
A: Still O(n²) because sum of 0..n-1 is n(n-1)/2.
Self-check
- What is complexity of double loop i,j from 0 to n-1?
- What is complexity of loop that halves n each iteration?
Pitfall: Inner loop to i still sums to O(n²)—triangular loops confuse many candidates.
Interview prep
- Nested 0..n-1?
O(n²) multiplications.
- Halving n loop?
O(log n) iterations.