Omitting Bases in Logs in Big O

Why we do not consider base of log in time complexity

Image for post
Image for post

For asymptotic complexity, base of logarithms does not matter, but why ?
In this article I plan on answering that question.

First we must look at the definition of Big O. A function f(n) is said to belong to O(g(n)) if and only if f(n) ≤ C*g(n) whenever n >k , where both k and C are constants.

f(n) ≤ C*g(n) whenever n > k

Image for post
Image for post
log base a of n
Image for post
Image for post
log base b of n

In order to show this our f(n) = log base a of n and our g(n) = log base b of n. This would give us the following equation.

Image for post
Image for post
Definition of Big O with log base a of n and log base b of n

We can choose values for C and k that would make the above equation true. I will choose C = log base a of b and k = 0. Now our equation will look like the following.

Image for post
Image for post
Big O equation with C= log base a of b and k = 0

Notice the right hand side of the equation (log base a of b times log base b of n). We can rewrite this equation thanks to the properties of logarithms.

Image for post
Image for post
The right side of the equation
Image for post
Image for post
The right side of the equation is equal to log base a of n

Notice that the right hand side of the equation (log base a of b times log base b of n) is exactly equal to log base a of n which is the value on the left hand side of the equation. So now we get the following equation.

Image for post
Image for post

The above equation is always true no matter what the values a, b or n are. Of course a and b must be greater than 1, and n must be greater than 0, so this is why the base doesn’t matter when dealing with Big O asymptotic.

If you would like to learn more about Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !

Image for post
Image for post

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Resources:

https://stackoverflow.com/questions/20709267/big-o-notation-log-base-2-or-log-base-10

https://www.quora.com/Why-we-do-not-consider-base-of-log-in-time-complexity

https://math.stackexchange.com/questions/37377/omitting-bases-in-logs-big-o

https://stackoverflow.com/questions/1569702/is-big-ologn-log-base-e

http://www.cs.cornell.edu/courses/cs211/2005sp/Lectures/L14-BigO/L14-15-Complexity.4up.pdf

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store