Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Logarithms and logarithmic time complexities used to confuse me for a very long time since it was one of those scary things in math where you see a symbol and then you get scared that it is something complex.

Logarithms are very simple. At the most fundamental level, the logarithm asks us a question.

log(8) with a base of 2 asks me: "what do I need to power 2 by to get 8? The answer is 3. 2^3 = 8

log(100) with a base of 10 asks me: "what do I need to power 10 by to get 100? The answer is 2. 10^2 = 100

This generalizes us to understand that a log asks us...what do I need to power my base by to get the number we are taking a log against?

That is what the logarithmic expression evaluates to.

Also, if we have 8 and a log base of 2, we can halve 8 3 times. 8 - 4 - 2 - 1 before we get to a 1 and we cannot cut in half anymore.

In standard mathematics, it is assumed that the base is a base of 10.

In computer science, the base is almost always 2. We will see why.


Where We See Logs In Computer Science:

Levels In A Binary Tree

In general, a binary tree with n nodes will have at least 1 + floor(log_2(n)) levels

When we do something like a tree traversal or heap insertion or removal this is why we use a bound of O(h) which for a balanced binary tree really means O(log(n)).

We will traverse at most a log amoung of levels in the asymptotic sense since that is our tail behavior. Our asymptotic behavior is logarithmic.


Merge Sort & Quicksort

In mergesort, we can only cut the input in half up to log(n) times.
Same for quicksort.

Each sorting algorithm will have log(n) levels of work roughly and then the question becomes what amount of work do we do in each of those levels.


Binary Search

In a binary search, we cut our search space in half every operation based on some predefined searching criteria we define for narrowing search space.

We can only cut our search space in half up to log(n) times.
The logarithm is critical for all of these applications since the question it asks is exactly what we are interested in.

++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Tuschar Roy:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Jarvis Johnson:    / vsympathyv  

Success In Tech:    / @successintech