base of logarithms in time-complexity algorithms

What is the base of logarithm on all time-complexity algorithms? Is it base 10 or base e?

When we say that the 开发者_Go百科average sorting complexity is O(n log n). Is the base of log n 10 or e?

---

In Computer Science, it's often base 2. This is because many divide and conquer algorithms that exhibit this kind of complexity are dividing the problem in two at each step.

Binary search is a classic example. At each step, we divide the array into two and only recursively search in one of the halves, until you reach a base case of a subarray of one element (or zero elements). When dividing an array of length n in two, the total number of divisions before reaching a one element array is log2(n).

This is often simplified because the logarithms of different bases are effectively equivalent when discussing algorithm analysis.

---

In Big-O complexity analysis, it doesn't actually matter what the logarithm base is. (they are asymptotically the same, i.e. they differ by only a constant factor):

O(log2 N) = O(log10 N) = O(loge N)

Most of the time when mathematicians talk about logs, they implicitly mean to base e. Computer Scientists would tend to favour base 2, but it doesn't actually matter.

---

In terms of Big-O, the base doesn't matter because of the change of base formula implies that it's only a constant factor difference.

However sometimes it's useful to count approximately how many operations an algorithm performs. In this case, most of the times it's base 2 due to the nature of most divide and conquer algorithms.

---

There's some explanation in this site

Basically, logarithms from base 10 or base 2 or base e can be exchanged (transformed) to any other base with the addition of a constant. So, it doesn't matter the base for the log.

The key thing to note is that log2N grows slowly. Doubling N has a relatively small effect. Logarithmic curves flatten out nicely. source

---

It varies depending on the problem and for the most part is irrelevant. However in many cases it is base 2, for example binary search is log(base 2)n. You can read about it in more detail here.