What is order of complexity here?

user_9921676 0
Viewed 64
   for(int i = n; i > 0; i/=3){
       for(int j = 0; j < i; j++){
           System.out.println("Hello");
       }
   }

Is it O(n) or O(nlog n)?

The outer loop will run log3 n times - as the iterator is getting factored by a constant of 3.

Thus, the outer loop will be called log3 n times

belongs to O(nlog n)?

data-structures complexity-theory time-complexity algorithm
1 Answers

This part n + n/3 + n/9 + ..... = n/3 (1 + 1/2 + 1/3 + ....) is not correct.

Actually

n + n/3 + n/9 + ..... = n( 1 + 1/3 + 1/9 +...)

and 1 + 1/3 + 1/9 + ... = a / (1-r) where a = 1 and r = 1/3

which converges to 3/2.

Therefore the complexity is O(n*(3/2)) or O(n)

Actually intuitively I would think like this: lets assume outer loop gives you a size of the input for a problem that you want to solve for. So the inner loop is like writing multiple for loops of varying sizes like below:

for ( k = 1 to n )

for ( k = 1 to n/3 )

for ( k = 1 to n/9 )

....

If you look at these for loops the complexity seems to converge to O(n) because the number of for loops depends on n and is diminishing, but if it were some constant like k then it would be O(n*k)

user_14103030
Related