44

When articles/question state that the Big O running time of the algorithm is O(LogN) .

For example Quicksort has a Big O running time of O (LogN) where the it is Log base 10 but Height of binary tree is O(LogN+1) where it is Log base 2

Question

1)I am confused over whether is it Log base 10 or Log base 2 as different articles use different bases for their Logarithm .

2) Does it make a difference if its Log base 2 or Log base 10??

3)Can we assume it mean Log base 10 when we see O(LogN)???

Computernerd
  • 7,378
  • 18
  • 66
  • 95
  • 4
    Typically textbooks and academic papers are implying `log_2 n` when they say `log n`. This is easiest to intuit when you consider one of the very first algorithms discussed in complexity classes: binary search. The entire premise of binary search is that it cuts your work in **half** at each step, and so the complexity of the algorithm is specifically `log_2 n`. Although any constant base might be valid when using `big-O` notation, it's never a bad idea to think about *why* the complexity is logarithmic. Is it because each step cuts your work in half? By ten? – dg99 Dec 20 '13 at 18:02
  • Depends on how many ways your decision stage yields per iteration in your algorithm. If it is 2, like check condition and either do this or do that than it is base 2 but if you take a decision with three outcomes than base 3 and so on. People say base doesn't matter but it does matter when you need to calculate `n Log(n)` for instance. – Redu Feb 23 '17 at 12:39

3 Answers3

54

I think it does not matter what is the base of the log as the relative complexity is the same irrespective of the base used.

So you can think of it as O(log2X) = O(log10X)

Also to mention that logarithms are related by some constant.

enter image description here

So

log₁₀(x) = log₂(x) / log₂(10)

So most of the time we generally disregard constants in complexity analysis, and hence we say that the base doesn't matter.

Also you may find that the base is considered to be 2 most of the time like in Merge Sort. The tree has a height of log₂ n, since the node has two branches.

1)I am confused over whether is it Log base 10 or Log base 2 as different articles use different bases for their Logarithm .

So as explained above this change of base doesn't matter.

2) Does it make a difference if its Log base 2 or Log base 10??

No it does not matter.

3)Can we assume it mean Log base 10 when we see O(LogN)???

Yes you can assume that provided you know the base conversion rule.

Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
16

log₁₀(x) = log₂(x) / log₂(10) for all x. 1/log₂(10) is a constant multiplier and can be omitted from asymptotic analysis.

More generally, the base of any logarithm can be changed from a to b (both constant wrt. n) by dividing by logₐ(b), so you can freely switch between log bases greater than one: O(log₁₀(n)) is the same as O(log₂(n)), O(ln(n)), etc.

An example consequence of this is that B-trees don't beat balanced binary search trees asymptotically, even though they give higher log bases in analysis. The just have better constants.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
10

In Big O notation, O(log(n)) is the same for all bases. This is due to logarithm base conversion:

log2(n) = log10(n)/log10(2)

1/log10(2) is just a constant multiplier factor, so O(log2(n)) is the same as O(log10(n))

dkrikun
  • 1,228
  • 1
  • 15
  • 23