What is the complexity(Ø) of this pseudo code?-CodePudding

My question is about finding the complexity of this algorithm. J value is related to n, so I'm confused about this.

What is the asymptotic complexity of this pseudocode?

for i=1 to n
  do
  j = 1;
  while (j < n)
    do
    j = j * 2;

Thanks.

CodePudding user response：

I believe it is O(n log₂n)

The outer loop is called n times and the inner loop is called log₂n times, since in every iteration, j is doubled. For first iteration, i.e., k=0; j is equal to 1 and goes on like 2, 4, 8, ... until 2^k>=n

CodePudding user response：

If I add a print at the end of the inner loop, I see:

(1,2,5)
(1,4,5)
(1,8,5)
(2,2,5)
(2,4,5)
(2,8,5)
(3,2,5)
(3,4,5)
(3,8,5)
(4,2,5)
(4,4,5)
(4,8,5)
(5,2,5)
(5,4,5)
(5,8,5)

So it appears O(n^2) but the inner loop appears constant so probably O(n) -- If the (j < n) part is switched to (j < i), that would be closer to O(n log(n)):

(2,2,5)
(3,2,5)
(3,4,5)
(4,2,5)
(4,4,5)
(5,2,5)
(5,4,5)
(5,8,5)