1
$\begingroup$

I was wondering what the time complexity of computing the natural log of a number is.

Note: I realize that the natural log of number is irrational, so my rephrased question would be "What is the Big-O of approximating ln(x) to d-decimal places?"

$\endgroup$
  • $\begingroup$ There are several ways to calculate first $d$ numbers of logarithm. Perhaps, their runtime is asymtotically different. $\endgroup$ – rus9384 Sep 18 '17 at 1:37
  • 4
    $\begingroup$ There are many algorithms for computing logarithms, see this question on Math.SE: math.stackexchange.com/q/61209/445911 So the "Big O" will vary by algorithm if that is what you're looking for. Alternatively you might be looking for the bit-complexity lower bound, in which case you made need to rephrase your question. $\endgroup$ – ryan Sep 18 '17 at 4:24
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Sep 18 '17 at 5:18
  • 2
    $\begingroup$ @ryan, wikipedia has a bit larger list for that. en.m.wikipedia.org/wiki/Logarithm#Calculation $\endgroup$ – rus9384 Sep 18 '17 at 6:50
  • $\begingroup$ There is no such thing as "The big O of computing something". First, big O is a measure of the rate of growth of mathematical functions. Asking "what is the big O of computing something?" is like asking, "What is the meters of Usain Bolt?" and expecting to be told his height. Or maybe the distance he runs. Who knows? Second, there is no such thing as "the big O of a mathematical function" -- asking for that is like asking "what is the number greater than ten?" Well, there are infinitely many of them. Which one do you want? $\endgroup$ – David Richerby Sep 18 '17 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.