2

This is pseudocode. I tried to calculate the time complexity of this function as this answer said. It should be like:

n + n/3 + n/9 + ...

Maybe the time complexity is something like O(nlog(n)) I guess? Or the log(n) should be log(n) base 3? Someone said the time complexity is O(n), which is totally unacceptable for me.

j = n
while j >= 1 {
    for i = 1 to j {
        x += 1
    }
    j /= 3
}
Community
  • 1
  • 1
JW.ZG
  • 611
  • 1
  • 7
  • 20

1 Answers1

6

The algorithm will run in:

n + n/3 + n/9 + ... = series ~= O(3/2 * n) = O(n)

since 3/2 is a constant. Here the k-th loop will run in n/3k steps.

Please notice the crucial difference from the linked question, where the outer loop runs n times and that is fixed.

gsamaras
  • 71,951
  • 46
  • 188
  • 305