# Omitting bases in Logs -> Big O

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?

• 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

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.

• 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.

First you must understand what it means for a function f(n) to be O( g(n) ).

The formal definition is: A function f(n) is said to be O(g(n)) iff |f(n)| <= C * |g(n)| whenever n > k, where C and k are constants.

so let f(n) = log base a of n, where a > 1 and g(n) = log base b of n, where b > 1

NOTE: This means the values a and b could be any value greater than 1, for example a=100 and b = 3

Now we get the following: log base a of n is said to be O(log base b of n) iff |log base a of n| <= C * |log base b of n| whenever n > k

Choose k=0, and C= log base a of b.

Now our equation looks like the following: |log base a of n| <= log base a of b * |log base b of n| whenever n > 0

Notice the right hand side, we can manipulate the equation: = log base a of b * |log base b of n| = |log base b of n| * log base a of b = |log base a of b^(log base b of n)| = |log base a of n|

Now our equation looks like the following: |log base a of n| <= |log base a of n| whenever n > 0

The equation is always true no matter what the values n,b, or a are, other than their restrictions a,b>1 and n>0.

So log base a of n is O(log base b of n) and since a,b doesn't matter we can simply omit them.