test series

Question

int i,j,k,s=0;

for(i=1; i<=n; i++)
  {

   for(j=1 ; j<=i; j=j*2)
    {
      for(k=n; k>1;k=k/2)
      {
        s++;
      }
    }
  }

What will be the time complexity of the above code?

Comments

TC= log n(log1 + log2 + log3+ ...+ logn)=log n(log n!)= log n(n log n)=n $(log n)^2$

Answer 1

The first loop with variable ‘i’ will run for ‘n’ times.
The second loop with variable ‘j’ will run for ‘$\log_{2} n$’ as ‘i’ will go upto n and j is multiplied by 2 i.e., it will be in terms of ‘n=$2^k$’.
The third loop with variable ‘k’ will run for ‘$\log_{2} n$’ as ‘k’ will go upto 1 by dividing itself by 2 i.e., it will be in terms of ‘n=n/2’.
therefore, TC = O(n$(\log_{2} n)^2$)

Comments

j loop is dependent on every value of i right? so how can we multiply both loops?

won’t the combined loop of i and j run for 1+2+3+..+logn(when i is n) so total log^2n times?

---

Yes, j loop is dependent on i.
Lets consider i=n then j will run until its value is less than or equal to i in powers of 2.
so in the maximum/worst case it will run for nlogn times.