8

While considering O(log(N)) for time complexity, what is the base of log?

Rob Hruska
  • 118,520
  • 32
  • 167
  • 192
sabika shamim
  • 81
  • 2

3 Answers3

15

All logarithms are related by some constant. (Hence the change-of-base formula). Because we generally disregard constants in complexity analysis, the base doesn't matter.

Usually, the base is considered to be 2, when deriving the algorithm. Consider a sort like merge sort. You can construct a tree out of it, and the tree has a height of log₂ n, because each node has two branches.

GManNickG
  • 494,350
  • 52
  • 494
  • 543
  • I would bold face the second sentence in the first paragraph ("the base doesn't matter") to make it an even better answer. – Hannes Ovrén Apr 11 '12 at 12:23
10

It doesn't matter, the relative complexity is the same regardless of the base used.

Rob Walker
  • 46,588
  • 15
  • 99
  • 136
  • Hmmm. If you logically extend this statement, you would be saying that O(n^2) is the same relative complexity as O(n^3). – Andrew Shepherd Nov 11 '09 at 04:55
  • Not at all. Big diff between 1 million squared or cubed. But log2, log10, log100? Not much difference at all. – cletus Nov 11 '09 at 04:56
  • @Andrew Shepherd - That is not correct. log_a(2n) / log_a(n) = log_b(2n) / log_b(n) for any a and b – mob Nov 11 '09 at 04:59
  • 3
    @Andres Shepherd: To expand on the other responses to your comment, log_a(n)/log_b(n) is a constant which is the same for all values of n. The ratio of (n^2)/(n^3), on the other hand, grows as n grows. Algorithmic complexity analysis is concerned with how resource requirements increase as n increases, so constants don't matter. Values that vary with n do. – Dave Sherohman Nov 16 '09 at 13:26
2

One way to think of it is that O(log2X) = O(log10X) = O(logNX)

RickNZ
  • 18,448
  • 3
  • 51
  • 66