What's the big O of this little code snippet?

Question

for i := 1 to n do
  j := 2;
  while j < i do
    j := j^4;

I'm really confused when it comes to Big-O notation, so I'd like to know if it's O(n log n). That's my gut, but I can't prove it. I know the while loop is probably faster than log n, but I don't know by how much!

Edit: the caret denotes exponent.

Answer 1

Looks like it is O(i log4 j) -- but it has been a while.

(log4 means log base 4)

Answer 2

Off the cuff, I'd guess is it is O(n slog₄ n) where slog represents the inverse of the tetration operator. Tetration is the next operation after exponentiation. Just like multiplication is iterated addition, and exponentiation is iterated multiplication, tetration is iterated exponentiation.

My reasoning is, if you multiplied j by 4 each iteration then the function would be O(n log₄ n). But since you are exponentiating it each iteration, you need a correspondingly more powerful operator than log: slog.

Answer 3

The problem is the number of iterations the while loop is executed for a given i.

On every iteration j:= j^4 and at the beginning j := 2, so after x iterations j = 24^x

j < i is equivalent to x < log_4(log_2(i))

I'd risk a statement, that the complexity is O(n * log_4(log_2(n)))

You can get rid of constant factors in Big O notation. log_4(x) = log(x) / log(4) and log(4) is a constant. Similarly you can change log_2(x) to log(x). The complexity can be expressed as O(n*log(log(n)))