CODEWITHSUNDEEP
algorithmruntimebig-o
user1246462
user1246462

Reputation: 1278

Big-O Notation regarding logarithms

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) = log5(x)

f(x) = log(x5)

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?

Upvotes: 5

Views: 23261

Answers (4)

Abraham Adam
Abraham Adam

Reputation: 633

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

Upvotes: 1

Ken Wayne VanderLinde
Ken Wayne VanderLinde

Reputation: 19349

This is a matter of math:

  1. f(x) = log5(x)
  2. f(x) = log(x5) = 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(log5(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))

Upvotes: 2

Yuushi
Yuushi

Reputation: 26040

I'll assume you mean f(n), not f(x). For 1 and 2, log^5(n) is equivalent to O(log log log log log(n)), while log(n^5) = 5 log(n) = O(log n).

For 3 and 4, I disagree. log(6*log n) = log(6) + log(log n) = O(log log n), which is the same as 4 - O(log log n).

Upvotes: 0

nneonneo
nneonneo

Reputation: 179422

  1. log5 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).

Upvotes: 8

Related Questions