Thread: Big oh problem #2

What is the big o of this code.


K=1;
do
j=1;
do
..
..

..
j=2*j;
while(j<=n);
k=k+1;
while (K<=n);

Originally Posted by Acessd23

What is the big o of this code.


K=1;
do
j=1;
do
..
..

..
j=2*j;
while(j<=n);
k=k+1;
while (K<=n);

The trip count for the inner loop is floor(log_2(n)+1)=O(log(n)), now the outer loop trip count is: .. ?

CB

the outer loop is N so

the answer is o(n*log(n)) ???