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?
 A: 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.
A: 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.
A: 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.
You can see a YouTube video on it here:
https://www.youtube.com/watch?v=MY-VCrQCaVw
You can read an article on it here:
https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca
