for (int i=1; i<=n; i*=2) { 
  for (int j=0; j<i; j++) { 
    for (int k=0; k<=n; k+=2) { 
      // Any O(1) operation 
    } 
    for (int k=1; k<n; k*=2) { 
      // Any O(1) operation
    } 
  } 
}

If you can truly understand the TC of the above code then this article is not for you. But if you have even a slightest of doubt in your solution then you need to know how complex TC can really be.

For starters lets take the most basic example. A loop inside a loop.

---

Example 1

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // Any O(1) operation
    }
}

In this case the outer loop runs n times, and the inner loop also runs n times. So TC is O(n) * O(n) = O(n²)

Pretty easy right, absolutely. But the most important thing to notice here is *(multiplication). Why are we multiplying. Do we always multiply when there is a nested loop (loop inside a loop). The answer is NO. TC inside a loop depends solely upon the number of iterations the loop is performing and not just bluntly multiplying the inner loop with outer loop. There is no short trick to find the time complexity, we have to think all the way through the loop that how many times it is iterating and that is the only way to find the TC.

So coming back to the above algo, how do we find its TC. It is by calculating how many times the loop is looping. So, lets start….

1st iteration (i = 0)

j = 0 to n-1 n times

2nd iteration (i = 1)

j = 0 to n-1 n times

3rd iteration (i=2)

j = 0 to n-1 n times

nth iteration (i=n)

j = 0 to n-1 n times

The total number of times this loop will run will be n+n+n+n+n….n times
So what will its summation be? We find that using AP (Arithmetic Progression) theorem.

$$Sn = n/2 [2a + (n-1)d]$$

Sn = sum of n terms, a = first term, n = number of terms, d = common difference

Sn => n/2 [2n +(n-1)0] = n/2 * [2n] = n²

Therefore, TC = O(n²)

You can argue that this method is way too obsolete and time consuming. YES it definitely is. But all this was just to show you why you multiplyed in the first place. However the problem here is that you resort to multiplication whenever you see 2 nested loops.

---

Example 2

for (int i= n; i > 0; i /= 2) {
    for (int j = 0; j<i; j++) { 
        // Any O(1) operation 
    }
}

Things take a really sharp turn when inner loop is dependent on outer loop. So, how do we calculate TC in that case. Lets understand by comparing algo in which the inner loop is dependent on outer loop and find out its TC.

To truly understand the whole concept of TC, you have to put away all your previous knowledge of TC aside and focus solely on what I’m stating below.

• Use multiplication when both loops run independently of each other.

• Use summation when the inner loop depends on the outer loop's value.

If you still don’t believe me use your current knowledge and solve this example. You will probably go on like this… 1st loop - O(log(n))… 2nd loop - O(n). So total TC by multiplying both is O(nlog(n)). WHICH IS COMPLETELY WRONG.

Let’s walk through the solution and find out its TC. As we can see that the inner loop is dependent on the outer loop, so instead of multiplying we apply summation to how many times the inner is going to run till the last value of the outer loop. So, lets start…

1st iteration (i = n)

j = 0 to n-1 n times

2nd iteration (i = n/2)

j = 0 to n/2 - 1 n/2 times

3rd iteration (i = n/4)

j = 0 to n/4 - 1 n/4 times

this goes on till i > 0
So as I said, we sum all the inner loop’s work that is n + n/2 + n/4 + n/8 + n/16 …..
What will its summation be? We find that using GP (Geometric Progression) theorem.

$$Sn = a(r^n-1)/r-1 ::(r ≠ 1) $$

$$Sn = a/(1-r)::(-1<r<1)$$

Sn = sum of n terms, a = first term, r = common ratio, n = number of terms

Here, r = (n/2 ÷ n) = 1/2, so we apply the second formula. Notice that the second formula is independent of n (number of terms), so it doesn’t really matter till where the value of ‘i’ goes.

Sn => n/(1 - 1/2) = 2n

Therefore, TC = O(2n) = O(n)

So now you know that we should never blindly multiply whenever we see a nested loop.
Now lets move on to the solution of the 1st algo and calculate its TC.

---

Boss Example

for (int i=1; i<=n; i*=2) { 
  for (int j=0; j<i; j++) { 
    for (int k=0; k<=n; k+=2) { 
      // Any O(1) operation 
    } 
    for (int k=1; k<n; k*=2) { 
      // Any O(1) operation
    } 
  } 
}

Notice the structure of the code carefully.
The first nested loop is dependent on the outer loop but the loops after that is independent of the outer loop’s value.
Also, nesting is till 2 levels only. The innermost loop is not nested.

Keep this in mind while solving.

• Use multiplication when both loops run independently of each other.

• Use summation when the inner loop depends on the outer loop's value.

1st iteration (i = 1)

j = 0 to <1 (1 time)

2nd iteration (i = 2)

j = 0 to <2 (2 times)

3rd iteration (i = 4)

j = 0 to <4 (4 times)

4th iteration (i = 8)

j = 0 to <8 (8 times)

nth iteration (i = n)

j = 0 to n-1 (n times)

We sum all the inner loop’s work that is 1+ 2+ 4+ 8+ 16…..n

As we see this sequence is in GP. So we calculate the sum using the first formula of GP. But that requires n (number of terms).
We calculate the number of terms this series contains. To find that we use the formula of GP.

$$Tn = ar^{n-1}$$

Tn = last term, a = first term, n = number of terms

In our case first term = 1, last term = n, common ratio = 2 and let number of terms = N

\=> n = 1 × 2^N-1 …*applying log on both sides*
\=> log(n) = (N-1) log(2)
\=> N = log₂(n) + 1

Now we calculate using the 1st formula of GP. Since r = 2, which fits the first formula.

$$Sn = a(r^{n}-1)/r-1$$

$$ Sn = 1*(2^{log_{2}n+1}-1)/2-1 $$

$$Sn =n*2 -1 = 2n-1$$

Therefore, The j-loop will run 2n - 1 times which is O(n).

The first k loop will run n/2 times which is O(n).

The second k loop will run log₂(n) time.

Now, since the k-loop is independent on its outer loop’s value, we multiply….. finally
O(n) * { O(n) + log₂(n) } = O(n²) + O(nlog(n) = O(n²) ignoring the lower value terms

And thus we get its Time complexity as O(n²)

Hope you all are wonderstruck by seeing how complex time complexity can really be. Now go on tackle those questions on TC and don’t forget to drop you curiosity in the comments.

GG