educative.io

Log2(n)*(4n-4) transformation for nested sum++

Courses
,
#1

Could you, please, explain me how to transform log2(n)*(4n-4) into (2n-1)?

for (int j = 0; j < var; j++) {
sum++;
}

1 Like
#2

Hi @MikeT

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your query, in the snippet that you are referring to, this loop is the inner loop from the given challenge. To calculate the time complexity of this loop, we can not ignore the outer loop.

int var = 1;
while(var < n) {
      for (int j = 0; j < var; j++) {
        ....
      }
var *= 2;
}

Let’s first focus on the outer loop. It depends on the variable var , which in turn depends upon n . And as you already pointed out, because var is multiplied by 2 at each iteration, the time complexity of the outer loop is O(log(n)). Now, the tricky part here is inside the inner loop. The reason is that it depends upon the variable j which depends upon var . So, saying that the inner loop is always O(n) would be a stretch. It is definitely O(var), but var has a different value at each iteration {1, 2, 4, 8, 10, 12, … , n}.
Therefore, in the challenge, we haven’t calculated the time complexity of the inner loop by itself (to be later multiplied with the outer loop). Instead , we have calculated the total time complexity of the inner loop, keeping track of its every iteration inside the outer loop. Later, we have added that complexity, instead of multiplying like we usually would.
Okay, time to break down the total iterations of the inner loop. As already mentioned, var has the values {1, 2, 4, 8, 10, 12, … , n}, so the total number of inner iterations are:
[1 +2 +4 +8 +10 + 12 + ... + n] \Rightarrow [2^0+2^1+2^2...+2^k] \text{,where} 2^k = n
\Rightarrow 2^{k+1}-1
\Rightarrow 2^{n}-1

This is how we derived the (2n - 1) that you are confused about. Now, the rest is pretty simple but let’s also explore that as well.

The derivation given above means that the inner loop has time complexity O(n). Now we add both the complexities:
O(n +log(n))
\Downarrow
O(n)

I hope my explanation has helped to clear your doubts.

Best Regards,

Fatimah Abdullah | Developer Advocate
Educative

1 Like
#3

@FatimahAbdullah Hello Fatima, thanks for the explanation, however on the 10th slide, on the top left corner it states that: "The outer loop is executed log2(n) times. Total = log2(n)(4n - 4) "

I think that statement is the root of the confusion, is that statement correct?

#4

Hi Fatimah,

Thanks for your explanation. However, as Surya pointed out, the confusion lies in 4n-4.

“This statement is executed 2(2n - 2) times due to inner loop”.

Could you explain why 2n-2 and not 2n-1 for sum++?

Cheers,
Berns

#5

Hi @Surya_Kiran_Valiveti and @Bernard_Cokee,

Thank you for reaching out to me again. Ah! I did not notice this explanation present in the slides before. We recently updated the explanation in the lesson and it seems this was left in the slides by mistake. I apologize for the inconvenience caused.
The correct runtime for sum++ is 2n-1.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative

1 Like