0

The internet has a lot of resources explaining Big-O for log-factorial function (e.g. 1, 2) which is O(n log(n)).

What I do not understand is why log() has O(log(n)) and not at least O(n). From the recursive code below, log_factorial is essentially called n times (which translates to log() being called n times), so if log() were O(n), log_factorial ought to be O(n^2).

log_factorial <- function (n) {
  # Return the log of factorial(n) for any integer n > 0
  if (n <= 1)
    return (0)
  return ( log(n) + log_factorial( n - 1 ) )
}

Looking up the internet did not help me much (on the contrary, it got me more confused). Wikipedia says Big-O of log should depend on the degree of precision:

...computing the natural logarithm (using the arithmetic-geometric mean) is O(M(n) ln n). Here n is the number of digits of precision at which the natural logarithm is to be evaluated and M(n) is the computational complexity of multiplying two n-digit numbers.

To get an empirical answer, I plotted runtimes vs n (below) and indeed, the log-factorial is not quadratic. Runtime in ms vs n

I am obviously missing something here and hope someone can explain to me. Pardon me if my question is 'noob-ish'.

NoviceProg
  • 815
  • 1
  • 10
  • 22
  • The plot you showed us very much looks like it could be bounded by `O(N*logN)`. It clearly isn't linear, but grows faster than that. – Tim Biegeleisen Mar 05 '18 at 08:17
  • What does median execution time have to do with the number of recursive calls? – Nir Alfasi Mar 05 '18 at 08:29
  • Did you just wonder why the complexity of calculating log(n) is `log(n)` ? :) – Nir Alfasi Mar 05 '18 at 08:29
  • @TimBiegeleisen, agreed. The plot is clearly not linear nor quadratic - it seems to be bounded by `O(N*logN)`, which (sort of?) confirms what is mentioned on the internet. – NoviceProg Mar 05 '18 at 08:43
  • The only doubt I would have here is how they arrived at `O(nlgn)`. – Tim Biegeleisen Mar 05 '18 at 08:44
  • @alfasin, it's actually part of an assignment and we were provided the recursive code and were told to give the time complexity. When I saw the code, my first instinct was `n^2`, that is, until I plotted the graph. Further research on the internet provided the answer, but I was still puzzled as to 'why' log(n) is `O(log(n))` – NoviceProg Mar 05 '18 at 08:46
  • @NoviceProg assuming you're not looking for high precision, meaning, the result of `log(n)` should be an integer, there are exactly `log(n)` steps to calculate log(n). For example: calculating log(2^10) should take exactly 10 steps (keep dividing by two until you reach 1). Now, of course that we can get philosophical about it and say that division by 2 is a simple shift operation while most divisions are more complex, and that's right, but when you calculate big-O complexity you calculate magnitude and what we're interested about is the asymptote convergence when the input is very large. – Nir Alfasi Mar 05 '18 at 08:55
  • 1
    @alfasin, oh crap... it's so obvious now that you pointed it out.... thanks for your thorough explanation! – NoviceProg Mar 05 '18 at 09:08
  • In your question you're confusing "log(n!) is O(n log n)" (a statement about the asymptotic behavior of a function) with "computing log(n!) takes time O(n log n)" (a statement about the asymptotic behavior of the runtime of a program). The question in your link (2) has the same problem -- and the answers explain why log(n!) is O(n log n) rather than talking about the runtime. As you correctly observe, the runtime depends on the desired accuracy and the costs of multiplications. – Paul Hankin Mar 05 '18 at 10:16

1 Answers1

1

TL;DR: There's no way to tell the Big-O of log(n), only of a specific implementation of log(n).

You're trying to reason about the Big-O of an algorithm that you didn't fully specify. Nobody knows what implementation you (or the various internet sources) have in mind for the logarithm function.

I'm quite sure that every half-decent log(n) implementation will perform better than O(n): log(1000000) won't take 1000 times longer than log(1000).

In the comments, there were plausible approaches given that perform log(n) in O(logn), and I think there can even be better ones.

For values in the range of a few thousands (as implied by your graph), I could even give you an O(1) solution with a table of precomputed log values.

Ralf Kleberhoff
  • 6,990
  • 1
  • 13
  • 7