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

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 ho开发者_JAVA技巧w much!

Edit: the caret denotes exponent.

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)))

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.