#ace TEST

Question

Comments

is it option b ?

Answer 1

Answer : D

Here observe that inner loop runs independent of value i, rather it depends on value of n.

So let's see first its complexity.

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

        k++;

}

Here k incremented by 1 in each step, and is added to j , after 1st iteration k is 2, then after 2nd step  k is 3, so in general after m interations j will have value as sum of first m nums. So breaking condition is m(m+1)/2 > n  ==> m = O(√n) 

Now outer loop : 

while(i>0){

      //inner loop code here

     i = i/2;

}

say this loop runs m times and as i divides by 2 and checked i>0 so least value is 1.

so after i = n/2^m and and i=1 for which it will iterate last i.e m => logn hence in total it takes logn+1 iterations 1 to break the condition.

So total complexity is outer loop * inner loop ==> √n (logn+1) ==> O(√nlogn).

Comments

Since k is being incremented by 1 in each iteration, variable j will first be incremented by 1, then 2, then 3 and so on till it remains less than n. This can be written as 1 + 2 + 3 + ... <= n So the inner loop will run atmost $\sqrt{n}$ times. The outer most loop runs $\log{n}$ times so overall complexity should be $O(\log{n}\sqrt{n})$

---

you are correct :)

---

I also found the same. but answer given was A. in these test series wrong answers is common now..