What big o is this small piece of code?

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 would like to know if it's O (n log n). This is my gut, but I can’t prove it. I know the while loop is probably faster than log n, but I don't know how much!

Edit: carriage indicates an exponent.

Answer 1

The problem is the number of iterations performed by the while loop for the given i .

At each iteration j:= j^4 and at the beginning j := 2 , therefore, after x iterations j = 2 4^x

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

I would risk asserting that the complexity is O(n * log_4(log_2(n)))

You can get rid of the constant factors in the 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) . Difficulty can be expressed as O(n*log(log(n)))

Answer 2

Turn off the cuff, I think it is O (n slog ₄ n ), where slog is the inverse of the operator . Tetration is the next operation after exponentiation. In the same way that multiplication is a repeated addition, and exponential is an iterated multiplication, a tetration is an iterative raising to a power.

My reasoning: if you multiplied j by 4 of each iteration, then the function would be O ( n log ₄ n ). But since you increment it every iteration, you need a more powerful statement than the log: slog .