educative.io

Time Complexity Difference between Challenge 3 and 4

Courses
, ,
#1

In challenge 4, time complexities of while and inner for-loop are multiplied :

while var < n:
print(pie)
for j in range(1, n, 2):
    sum += 1
var *= 3

Where as for challenge 3, they are added:

while var < n:
print(pie)
for j in range(var):
    sum += 1
var *= 2

Could someone explain why there is a difference in these two cases ?

In “Common Scenarios for complexities” a similar nested structure had time complexities multiplied and not added:

for i in range(n):
   for x in range(i):
#2

@Javeria_Tariq Could you please look into this ? I’m still not clear on these concepts , and been waiting for a while for clarification. Your pointers are much appreciated.

Thanks !

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5674196654882816

#3

@Javeria_Tariq , any update on this ?

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5634360497668096

#4

Hi @Amit_Adiraju_Narasim !
Thanks for your patience. We used summation in the second example because the Time Complexity for the inner loop in the second example is dependent on the outer loop.
In the second algorithm, with n = 2k, the outer loop is executed k times (i.e., log n). The inner for loop loops over range(var), and since the consecutive values of var are 1, 2, 4, … , 2k (actually the last one is missing because it’s var < n not var <= n but let’s include it, which is definitely not worse), the sum += 1 line is executed 1 + 2 + 4 + … + 2k = 2 × ( 2k ) - 1 times. O(2 × ( 2k ) - 1) = O( 2k ) = O(n).
I hope it helps. Happy Learning :blush:

#5

Thanks for the explanation. It gave me good difference between Challenge 4 and Challenge 3. However, I’m still not clear on why “Common Scenarios for complexities” are multiplied.

In both cases( Challenge 3 and common scenarios ), it looks like , based on the outer loop value the inner loop is changing, shouldn’t we add TC’s there are well , by this logic ?

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5757443858497536

#6

Hi @Amit_Adiraju_Narasim !
Thanks for contacting the Educative team.
In this case, the bottleneck of the algorithm is the sum += 1 line. It is O(1) by itself, of course, so the question is: how often is that line executed? The time complexity of the inner loop is dependent on the outer loop because of the variable var. For the first iteration of the outer loop, the inner loop code (sum += 1) executed 1(2^0=1) time, for the second iteration, it executed 2(2^1=2) times, and for 3rd iteration, it executed 4(2^2=4) times and so on. Here its complexity is totally dependent on the outer loop.
We can find the time complexity of the algorithm by finding out the number of times a code (common to both loops i.e, in this case (sum += 1)) is executed. So, the sum += 1 line is executed 1 + 2 + 4 + … + 2k = 2 × ( 2k ) - 1 times. O(2 × ( 2k ) - 1) = O( 2k ) = O(n) .
Similarly, for the following code, the bottleneck of the algorithm (challenge 4) is the sum += 1 line. Here, we loop over range(1, n, 2), and this line is executed n (here 5) times for each iteration of the outer loop. But that’s O((n - 1)/2) = O(n) independent of the value of var. So we get O(n) + O(n) + … + O(n), with one term per iteration of the outer loop, which we established is O(log n), hence O(log n) × O(n) = O(n log n).

while var < n:
    print(pie)
    for j in range(1, n, 2):
        sum += 1
    var *= 3
print(sum)

I hope it helps. Happy Learning :blush:

1 Like