Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
1  
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
1  
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
1  
@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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.