Big-O Notation regarding logarithms

Question

I got asked an interview question that wanted me to discern the Big-O notation of several logarithmic functions. The functions were as follows:

f(x) = log⁵(x)

f(x) = log(x⁵)

f(x) = log(6*log x)

f(x) = log(log x)

I was told that the Big-O for the first and second are not equivalent and the third and fourth are not equivalent after mistakenly guessing the opposite. Can anyone explain why they are not equivalent and what their Big-O are then?

Solution 1

1. log⁵ x is the same as writing log log log log log x, which is a very slow-growing function of x.
2. This is equivalent to 5 log x (rewriting exponentiation inside the log as multiplication outside), which is equivalent to log x.
3. This is equivalent to log 6 + log log x, which is equivalent to log log x.
4. This is just log log x.

So you have O(log log log log log x), O(log x), O(log log x) and O(log log x), three distinct Big-O classes.

If your interviewer said 3 and 4 were different, either he was mistaken or you've misremembered the question (happens all the time).

Solution 2

This is a matter of math:

1. f(x) = log⁵(x)
2. f(x) = log(x⁵) = 5 * log x
3. f(x) = log(6*log x) = log 6 + log(log x)
4. f(x) = log(log x)

So the Big O is

1. O(log⁵(x))
2. O(log x)
3. O(log (log x))
4. O(log (log x))

So (1) and (2) aren't equivalent, but (3) and (4) are (though they're different from both (1) and (2))

Solution 3

f(x) = log^5(n)
f(x) = log(n^5) -> 5 log(n)
O(5 log(n)) < O(log(n)^5)

f(x) = log(6*log n) -> log(6)+log(log(n))
f(x) = log(log n) 
log(log n) < log(6) + log(log(n)) 

, although log(6) is a constant so they have same O

Comments

[Yuushi]

2. should be 5*log x, not log 5 + log x (although in this case they have the same order).

[nneonneo]

Yes, you are right. I misread...thought it was log(5x) for some reason.

[user1246462]

And log⁵x is not equivalent to (logx)⁵ correct?

[nneonneo]

Yes, that's right. log^5 is 5 iterated applications of log; log(x)^5 is log(x) to the fifth power. They are of different orders.

[user1246462]

log(x)^5 would thus exhibit faster growth than log^5x?

[nneonneo]

Much faster. log^5 x grows slower than log^4 x, which grows slower than log(x), which is slower than log(x)^5.

[DSM]

Huh! I would have read log^5(x) differently, not as an iterated log, but just as (log(x))^5, rather like I'd read sin^2(x) as (sin(x))^2) and never as sin(sin(x)).

[nneonneo]

This is a matter of mathematical convention. Over at math, the suggestion is that your interpretation is correct w.r.t log and trig. From my math classes, IIRC, we tended to use the exponentiation interpretation only for trig functions, and not for log...

[jogojapan]

I find this way of interpreting log^5(x) most unusual. Although in algebra, notations like f^5(x) for 5 nested applications of f to x are used, I don't think this is usually done in the context of computer science. I'd take it to mean (log x)^5.