CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
user438293456
user438293456

Reputation: 596

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 how much!

Edit: the caret denotes exponent.

Upvotes: 4

Views: 702

Answers (2)

Maciej Hehl
Maciej Hehl

Reputation: 7995

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

Upvotes: 13

John Kugelman
John Kugelman

Reputation: 361927

Off the cuff, I'd guess is it is O(n slog4 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 log4 n). But since you are exponentiating it each iteration, you need a correspondingly more powerful operator than log: slog.

Upvotes: 2

Related Questions