complexity

Question

Answer 1

Answer is O(nlogn) while loop depends on i which is reduced by 2 so while loop run logn times . For loop run approx n times for each i value. so total = n $\times$ logn= O(nlogn)

Answer 2

it can be rewritten as 

for(i=n;i>0;i/=2)

{

k=1;

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

k++;

}

---------------------------------------------------

outer for loop execution

1st iteration i=n

2nd iteration i=n/2

3rd itearation i=n/4

.

.

kth iteration i=n/2^k;

so n/2^k>0  equate to for loop condition)

n/2^k=1 then k=log(n).

coming to inner for loop.

for j=1,2,3,....n .it executes 'n' times.

so total time complexity is o(nlog(n))