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

Time:10-20

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.

  • Related