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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Please accept some of the previous answers you received. This will make it more likely that people will keep providing you with good answers. $\endgroup$ – Rasmus May 6 '11 at 9:43
  • $\begingroup$ What do you mean with "base"? $\endgroup$ – Rasmus May 6 '11 at 9:44
  • $\begingroup$ e.g. Ln -> base = 'e' $\endgroup$ – user9492 May 6 '11 at 9:50
  • 1
    $\begingroup$ See my answer here: math.stackexchange.com/questions/33820/big-oh-question/… $\endgroup$ – Raphael May 6 '11 at 12:00
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you show me a proof? or mathematical definition? $\endgroup$ – user9492 May 6 '11 at 9:49
  • $\begingroup$ See here. $\endgroup$ – Rasmus May 6 '11 at 9:56
  • $\begingroup$ Can you see the EDIT $\endgroup$ – user9492 May 6 '11 at 10:58
  • 1
    $\begingroup$ @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. $\endgroup$ – dsolimano May 6 '11 at 12:17
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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