educative.io

Educative

Common Complexity Scenarios

For this snippet

for (int i = 1; i <= n; i *= 2) {

for (int j = 0; j < i; j++) {
    // Statement(s) that take(s) constant time

}
}

I didn’t understand why the complexity is O(n+logn), instead it should be O(nlogn).

Hi @Sai,

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

In response to your query, you referred to the following code snippet:

for (int i = 1; i <= n; i *= 2) {
    for (int j = 0; j < i; j++) {
        // Statement(s) that take(s) constant time
    }
}

As we can see, the inner loop in this code is dependent on the outer loop. We will first focus on the outer loop. It depends on the variable i , which in turn depends upon n . An, because i is multiplied by 2 at each iteration, the time complexity of the outer loop is O(lg(n)).
Now, the tricky part here is inside the inner loop. The reason is that it depends upon the variable j which depends upon i. So, saying that the inner loop is always O(n) would be a stretch. It is definitely O(i), but i has a different value at each iteration. These values will be: {1, 2, 4, 8, 10, 12, … , n}.

Therefore, 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. In simpler words, usually, we calculate how many times the inner loop would execute inside one iteration of the outer loop. However, this number is not constant in this case, therefore, we will calculate the total number of executions of the inner loop in the whole program. I hope you understand this now.

Okay, time to break down the total iterations of the inner loop. As already mentioned, i 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] => [20 + 21 + 22 + … + 2k], where 2k = n
=> 2k+1 -1
=> 2n - 1

This is how we derived the (2n - 1). This will be the total running time of the inner loop in the whole program (not just one iteration of the outer loop).

Now, we will add both the complexities because we have calculated them separately.
O(n + log(n)) => O(n)

I hope my explanation has helped you understand this concept in a better way.

Best Regards,

Fatimah Abdullah | Developer Advocate
Educative

3 Likes

How did you go from 2^k = n to below

=> 2k+1 -1
Below I understood, as it is because (2^k x 2) - 1, then replacing 2^k with n, we have
nx2 - 1
=> 2n - 1

Actually I am looking for the explanation of this section but I could not find any question. This is the closest to the below section I want to understand.

Nested For-loop With Index Modification

for (int i=0; i<n; i++){    i*=2;    for (int j=0; j<i; j++){        // Statement(s) that take(s) constant time    }}
1 Like

It is a geometric series which replaced with inner loop iteration.
Please check below link

https://en.wikipedia.org/wiki/1_%2B_2_%2B_4_%2B_8_%2B_⋯