14 views

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

for example,

Q1>

     int i,j;
      for(i=1;i<n;i=i++)

{

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

Q2>

            int i,j;
for(i=1;i<=n/2;i=i++)
{
for(j=1;j<=i;j++)
}

ago | 14 views

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:

Q1

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))$$

Q2

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
+1

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)

+1
Yes that would be correct
0
Thank You Sir