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