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

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.

algorithmtime-complexitybig-ocomplexity-theory


Solution 1:[1]

I believe it is O(n log2n)

The outer loop is called n times and the inner loop is called log2n 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 2k>=n

Solution 2:[2]

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)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2

Related Questions