Analyzing Time Complexity of Multiple Consecutive Loops
Learn how to correctly evaluate the time complexity of algorithms containing multiple independent and nested loops in succession.
The Add vs Multiply Rule
When analyzing a complex function with 5 different loops, beginners often panic and throw out wild guesses. The reality is that combining loop complexities follows two very strict, simple mathematical rules: Adding and Multiplying.
Rule 1: Multiply Nested Loops
If a loop is inside another loop, their complexities multiply.
for (int i = 0; i < N; i++) { // O(N)
for (int j = 0; j < M; j++) { // O(M)
print("Hello");
}
}
The inner loop runs M times for every 1 iteration of the outer loop. Total Time = O(N * M).
Rule 2: Add Consecutive Loops
If a loop is after another loop (at the same indentation level), their complexities add.
for (int i = 0; i < N; i++) { print(i); } // O(N)
for (int j = 0; j < N; j++) { print(j); } // O(N)
The computer finishes the first loop entirely before starting the second. Total Time = O(N) + O(N) = O(2N). Applying the rule of dropping constants, it simplifies to O(N).
Combining Both
What if you have a nested loop followed by a single loop?
// Nested Block
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) { ... }
}
// Single Block
for (int k=0; k<N; k++) { ... }
- The Nested Block is O(N^2).
- The Single Block is O(N).
- They are consecutive, so we add: O(N^2 + N).
- Apply the rule of dropping non-dominant terms: O(N^2).
The Takeaway
Break down large algorithms visually. Group nested loops into single multiplied blocks. Group consecutive blocks with addition. Finally, ruthlessly drop all constants and small terms to find the true Big O.
You add their complexities together. O(N) + O(N) = O(2N), which is simplified by dropping the constant to O(N).
You multiply them only when one loop is nested completely inside the body of another loop.
If Loop A iterates over array size N, and Loop B iterates over array size M, the complexity is O(N + M). You cannot drop one because you don't know which is larger.
No, adding 5 loops makes it O(5N). Dropping the constant makes it O(N). You only get exponents (like N^2) by nesting loops.
You add them: O(N + log N). Because linear time (N) grows much faster than logarithmic time (log N), N is dominant. The final complexity is just O(N).