Awesome q2a theme
0 votes

Can Someone help me understand the time-complexity of dependent loops?

for example,


     int i,j;


                    for(j=1;j<=i;j=j*2) }



            int i,j;


ago in Algorithms by (21 points) | 14 views

1 Answer

+2 votes
Best answer

Whenever there are dependent loops given you can resolve them in two ways:

  • Direct way (Eyeballing it)
  • Resolve the loops concurrently

Direct way: Let’s say we are solving Q1, the inner loop is looping from j = 1 to j = i and it takes multiplicative jumps (j *= 2), so it will take $log_2(i)$ steps, now what’s the maximum value i can take? i can be max n – 1, so complexity of inner loop is O(log(n)) and now take the outer loop as independent, it will have complexity O(n), so total complexity = O(nlog(n))

Similarly for Q2, inner loop will have complexity O(i), i will take maximum value n/2, so complexity of inner loop = O(n), complexity of outer loop is also O(n), so total complexity $O(n^2)$.

Resolving the loops concurrently: 


For i = 0, inner loop will run 0 time

For i = 1, inner loop will run 1 time

For i = 2, inner loop will run 2 time




For i = n-1, inner loop will run approximately log(n) times

Total times both loop will run is $$\sum_{k=0}^{n-1}log(k) = log(n!) = O(nlog(n))$$


For i = 1, inner loop will run 1 time

For i = 2, inner loop will run 2 times




For i = n/2, inner loop will run n/2 times

Total times both loop will run is $$\sum_{k=1}^{\frac{n}{2}}k = \frac{\frac{n}{2}(\frac{n}{2} + 1)}{2} = O(n^2)$$

ago by (2.9k points)
selected ago by

Thanks a ton, regarding the second method (Resolving the loops concurrently) : if we would have the second for loop’s expression3 as ‘j++’ instead of‘j*2’,the complexity would be O(n^2)

Yes that would be correct
Thank You Sir
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,953 questions
3,113 answers
95,780 users