Take the 2-minute tour ×

Can anyone explain, with the aid of a mathematical proof, why bases are omitted in Big - O notation?

EDIT: I don't understand how:

NB: $\log_2(n) =$ log to the base 2 of n

$log_2(n) = \log_k(n)/\log_k(2)$

proves that bases are omitted in Big O...please can some explain?

share|improve this question
Please accept some of the previous answers you received. This will make it more likely that people will keep providing you with good answers. –  Rasmus May 6 '11 at 9:43
What do you mean with "base"? –  Rasmus May 6 '11 at 9:44
e.g. Ln -> base = 'e' –  user9492 May 6 '11 at 9:50
See my answer here: math.stackexchange.com/questions/33820/big-oh-question/… –  Raphael May 6 '11 at 12:00

2 Answers 2

up vote 9 down vote accepted

Changing the base of a logarithm corresponds to multiplication by a constant, but big O is only defined up to a constant. Therefore the base does not make a difference in that case.

share|improve this answer
Can you show me a proof? or mathematical definition? –  user9492 May 6 '11 at 9:49
See here. –  Rasmus May 6 '11 at 9:56
Can you see the EDIT –  user9492 May 6 '11 at 10:58
@user9492, looking at your edit, log base k of 2 is just a constant number, right? So all we're doing is dividing by some constant c to get to any base that we want. And, constants are ignored in big O notation. –  dsolimano May 6 '11 at 12:17

Surely $\mathcal{O}(f(x))$ is a equivalence class so we are done if we can show that all logarithms are in $\mathcal{O}(\ln(x))$ (logarithm to the natural base). We write $g(x) \in \mathcal{O}(f(x))$ if there is a $C \geq 0$ such that $|g(x)| \leq C\cdot |f(x)|$ for all $x \geq x_0$ with some real $x_0$.

Let $b$ be your favourite base, we have that

$\log_b(x)=\frac{\ln(x)}{\ln(b)}$ it directly follows that $|\log_b(x)| \leq C \cdot |\ln(x)|$ where $C=\frac{1}{|\ln(b)|}$ and therefore immediately that $\log_b(x) \in \mathcal{O}(\ln(x))$ and the whole theorem.

share|improve this answer

Your Answer


