Title | : | Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science |

Duration | : | 10:24 |

Viewed | : | 281,479 |

Published | : | 30-01-2019 |

Source | : | Youtube |

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: 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

SPONSORED

RELATED VIDEOS

Asymptotic Notations 101: Big O, Big Omega, & T... 23:16 - 309,649 |

Про GitHub Actions за 10 минут 10:12 - 9,740 |

Big-O Notation - For Coding Interviews 20:38 - 363,538 |

Why The Logarithm Is So Important For Algorithm... 10:05 - 92,862 |

Why Is Merge Sort O(n * log(n))? The Really Rea... 36:50 - 111,297 |

The Ultimate Big O Notation Tutorial (Time & Sp... 17:20 - 164,955 |

Big O: How Code Slows as Data Grows 27:46 - 62,645 |

What Is Asymptotic Analysis? And Why Does It Ma... 08:05 - 78,389 |