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

>> YOUR LINK HERE: ___ http://youtube.com/watch?v=M4ubFru2O80

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

#############################

New on site