2
$\begingroup$

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?

  • 1
    See my answer here: http://math.stackexchange.com/questions/33820/big-oh-question/33906#339062011-05-06

3 Answers 3

9

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.

  • 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.2011-05-06
3

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.

0

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