j = n; while (j>=1) { i = j; while (i <= n) { cout<<"Printed"; i*= 2; } j /= 2; }

My goal is finding T(n) (function that gives us number of algorithm execution) whose order is expected to be n.log(n) but I need exact function which can work fine at least for n=1 to n=10 data

I have tried to predict the function, finally I ended in ***T(n) = floor((n-1) log(n)) + n**

which is correct just for n=1 and n=2.

I should mention that I found that inaccurate function by converting the original code to the for-loop just like below :

for ( j = 1 ; j <= n ; j*= 2) { for ( i = j ; i<= n ; i*=2 ) { cout << "Printed"; } }

Finally I appreciate your help to find the exact T(n) in advance. 🙏

## Answer

using `log(x)`

is the floor of log based 2

1.)
The inner loop is executed `1+log(N)-log(j)`

the outer loop executed times `1+log(N)`

with j=1,2,4…N times the overall complexity is `T(N)=log(N)log(N)+2*log(N)+1-(log(1)+log(2)+log(4)...+log(N))= log(N)^2-(0+1+2+...+log(N))+2*log(N)+1= log(N)^2-log(N)(log(N)-1)/2+1= log(N)^2/2+3*log(N)/2+1`

2.) same here just in reverse order.

I know it is no proof but maybe easier to follow then math : godbolt play with n. it always returns 0;