Self doubt :Time Complexity -Iterative

Question

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++)
            }

       

Answer 1

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

Comments

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