Big oh problem #2

Acessd23 · #1 $Old$ October 16th, 2009, 12:18 AM

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);

CaptainBlack · #2 $Old$ October 16th, 2009, 12:25 AM

Quote:

Originally Posted by Acessd23 $View Post$

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

Acessd23 · #3 $Old$ October 16th, 2009, 12:28 AM

the outer loop is N so

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