What's the time-complexity function [ T(n) ] for these loops?

Question

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 1

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;