2

Textbook reads:

All logarithms are natural logarithms: $\log = \ln$.

Does this mean $n\log(n) = n\ln(n)$?

Ali Caglayan
  • 5,726
A_for_ Abacus
  • 1,899
  • @A_for_Abacus That phrase is a terrible phrase to teach computer scientists. In --most-- cases, our "log" is base 2, not e or 10. For instance, the "log" in the traditional merge sort's n log n is base 2. With a phrase like that, I'd start to question everything in that book (even more so than the standard academic question everything stance). – corsiKa Oct 23 '14 at 17:45

5 Answers5

7

If the textbook is making clear that you should read $\log n$ to mean $\ln n$, then yes, barring any subscript for a base other than $e$, $n \log(n) = n\ln(n)$.

amWhy
  • 209,954
  • I agree with the sentiment of this answer, and you should - they've made it clear they're using the two interchangeably. It should be noted, however, that in the context of OP (using this for computational complexity) such a phrase is a dangerous one and probably should be avoided. I hope they supplied a significant amount of background about how complexity analysis works, and a justification of how they arrived at such a seemingly terrible decision. – corsiKa Oct 23 '14 at 17:47
  • @corsiKa Notice that often there is a hidden constant in factor (like in $O(log(n))$), so it's harmless to use natural log. Also, logarithm in base $2$ is often denoted $lg$ instead of $log$ or $ln$. – Jean-Claude Arbaut Oct 23 '14 at 17:54
  • That constant is probably the rationale for them using ln everywhere. It's just a bit misleading to say it's always the natural log, when log2 and log10 are much, much more common in a typical algorithms course. – corsiKa Oct 23 '14 at 18:58
5

If $\log = \ln$, then yes, indeed, $n\log n = n\ln n$.

Note, however, that this is utterly unimportant if you are looking at it from the case of the big $O$ notation, which is highly likely, since

$$n\log n \in O(n\ln n)$$ and $$n\ln n \in O(n\log n)$$ or, in other words, $$O(n\log n)=O(n\ln n)$$

5xum
  • 123,496
  • 6
  • 128
  • 204
  • Completely agree - I could see a function similar to atoi being based on the base of the number being parsed, but thanks to the math behind logarithms they're all in the same base. It's not like you'd have O(n log-k n) - it would just be O(n lg n) no matter if it was base 2, e, 10, or 36. – corsiKa Oct 23 '14 at 17:42
3

Normally, the base of a logarithm must be specified as $\log_a$. A very common convention is $\ln \equiv \log_e$.

However, $\log$ without subscript can mean a few different things based on the context (and therefore must be always explicitly stated).

$\log \equiv \log_{10}$, is very common in many mathematical books and publications.

$\log \equiv \log_2$, in computer science.

$\log \equiv \ln$, in most physics and applied mathematical contexts.

Your textbook is in the latter category. It can still use other bases for logarithms, but unspecified means base $e$.

Sebastiano
  • 7,649
patatahooligan
  • 522
  • 4
    Mathematical books and publications universally use $\log \equiv \ln$ (at least, past the middle- or high-school level, where it can be assumed that the reader is familiar with $e$); there's no mathematical reason to use $10$ as a base for the logarithm instead of $e$, which conveniently has $(\log x)' = 1/x$. Some engineering texts, or more generally texts that involve lots of numeric computation, might use $\log\equiv \log_{10}$. – anomaly Oct 23 '14 at 14:54
  • Some domains of mathematics may make the implicit assumption of $\log \equiv \ln$ but given the dominates of the decimal number system, $\log_{10}$ often is convenient, and will use $\log \equiv \log_{10}$. In my experience any textbook in mathematics or computer science will explicitly mention which based is the default assumption for $\log$ when not specified. – mctylr Oct 23 '14 at 17:41
  • 1
    @mctylr $\log_{10}$ may be convenient in some contexts, even in some mathematical contexts, but the overwhelming majority of mathematics uses $\log$ to denote the natural logarithm. Mostly without even mentioning it, since it is so natural. – Daniel Fischer Oct 23 '14 at 17:43
  • @anomaly Actually I have very rarely come across the $\log \equiv \ln$ case because $\ln$ is already a shorter way to write it. In textbooks I've used so far $\log$ goes to the next most useful base which is either $10$ or $2$ depending on the context. Maybe usage varies by region and time period. – patatahooligan Oct 23 '14 at 17:50
  • Any specific textbooks in mind? It's not that I don't believe you; I've just literally never seen $\log\equiv \log_{10}$ since high school (see also: $\div$). I've seen a few calculus tests use $\ln$ consistently, but $\log$ is vastly more common in my experience. There's just no reason to ever use $\log_{10}$ unless you're going through a pile of numerical computation with large numbers, which is not something that comes up in math. – anomaly Oct 23 '14 at 17:56
  • @anomaly After some more research, it seems that $\log \equiv \log_{10}$ might mostly be an engineering thing (I'm an electrical engineer) and I assumed it was more common than it actually is because our classes always worked with the assumption that $\log \equiv \log_{10}$ and $\ln \equiv \log_e$. – patatahooligan Oct 23 '14 at 18:12
1

It just means that unless some other base is specified, the base of the logarithm is assumed to be $e$. That is, if you see $\log x$, the author means $\log_e x$, which can also be written $\ln x$.

The rule $\log_b x^n = n\log_b x$ holds for any base $b > 0$, with $b \neq 1$. In particular, it holds for $b = e$, so the answer to your question is yes.

N. F. Taussig
  • 76,571
0

Yes. These notations are same. For example $\log x=\ln x$.

Paul
  • 20,553