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
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Видео Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
Видео Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)Why Is Merge Sort O(n * log(n))? The Really Really Long Answer.Asymptotic Bounding 101: Big O, Big Omega, & Theta (Deeply Understanding Asymptotic Analysis)Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal.Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)The Science of Six Degrees of SeparationLearn Big O Notation In 12 MinutesBig O Notation - Code ExamplesBig O Notation Series #4: The Secret to Understanding O (log n)!What Is Big O Notation?Logarithms explained Bob Ross styleTotal Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)What Is Asymptotic Analysis? And Why Does It Matter? A Deeper Understanding of Asymptotic Bounding.Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)5 Problem Solving Tips for Cracking Coding Interview QuestionsBig O: How Code Slows as Data Grows1.5.1 Time Complexity #1Quadratic and Logarithmic Time Complexity - Data Structures and AlgorithmsDepth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms