Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science @BackToBackSWE
Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science  @BackToBackSWE
Uploaded January 2019 | Updated November 2026, 3 hours ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: 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: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Deeply Understanding Logarithms In Time Complexities & Their Role In Computer ScienceEdit Distance Between 2 Strings - The Levenshtein Distance (Edit Distance on LeetCode)The Recursive Staircase - Top Down & Bottom Up Dynamic Programming (Climbing Stairs on LeetCode)Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively)Clone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space SolutionTotal Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)Implement An LRU Cache - The LRU Cache Eviction Policy (LRU Cache on LeetCode)Depth First & Breadth First Graph Search - DFS & BFS Graph Searching AlgorithmsSearch A Maze For Any Path - Depth First Search Fundamentals (Similar To The Maze on Leetcode)Why Comparison Based Sorting Algorithms Are Ξ©(n*lg(n))Implement A Queue Using Stacks - The Queue ADT (Implement Queue Using Stacks on LeetCode)
Back To Back SWE |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER