Awesome q2a theme
0 votes
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 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: 

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 by
+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
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
14,322 comments
95,780 users