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

all right so in today's video we are going to discuss logarithms in time complexities so this is something that confused me for a very long time and if this is something you're already familiar with you don't really need to watch this you probably already know but there's certain instances when we're deducing complexities with like things like binary search we'll see things like merge sort quicksort where we see a logarithm appear in the complexity and my goal by the end of this video I want you to have a full and intuitive understanding of what a logarithm means and why it is useful for us and the question it asks us when we are declaring your complexity using the logarithm so let's first investigate what a logarithm is and the fundamental question that a logarithm asks us so I want you to get again the intuitive understanding of this a logarithm asks us a question so I want you to look at this log base two of eight so what does this logarithm ask us it asks the base of two what do I need to power the base of two by two gets the number in the parenthesis eight well that answer is that answer is three so why is it three let's look at what we're actually doing so do you see how we're doing three divisions until we get down to one we go from eight to four that's one cutting in half we go from four to two that's cutting in half again and then we go from two to one and you see we cut in half three times this three looks familiar that's the three we just got there so does that ring a bell so the thing is that's why a log base two is considered cutting in half we are performing divisions by two divisions by two so they longer them is a expression of a having when it is under the base of two in computer science we most often use the log base two in fact we almost always use log base two but in general mathematics you're going to see log base ten most of the time and this is what you'll see you'll see nothing so when you're doing calculus you're always going to assume a log base ten this is just the general thing with normal mathematics but when you're in computer science you'll also see you'll also see the two is not there so the thing is it's always the implied context that the base is going to exist in so when we're doing calculus we'll just assume it's log base ten when we're doing computer science we'll assume it is log base two and we're going to see why that is the case most of the time anyway let's look at the second example now we're looking at log base ten we're looking at log base ten and what does this ask me I don't want you to look at this what does that ask me that asks me my base is ten what do I need to power 10 by to get the value 100 well the power in to power 10 by to get the value of 100 is it's going to be 2 so 10 squared is going to be a hundred so the thing is what a logarithm is asking is it's asking are we doing are we going to be having are we going to be tempting it's it's all about powers and calculating exponential quantities so when we're doing a log base 2 we want to see how many times did I multiply but we're divided by 2 to get to a certain value this is like the intuition behind it so this is what it would look like for the having for the log base of 2 so for the log base of 10 this is what it would look like so do you see how we just tend to times we just cut tenths twice we cut halves three times hence the 3 hence the two this is what a logarithm is all about remember it's all about what do we want to power the base by to get the number in the parentheses so where does this appear in computer science and why do we care about this so let's investigate further so here is a case where our logarithmic time complexity is going to be familiar to us when we're dealing with any binary structure like a binary tree of sorts so we're going to have at least one plus the floor of log nine levels if we have and notes and is 9 in this case if we actually do the math and remember we're using log base 2 because in computer science we always use log base 2 implicitly we just assume it's going to be log base 2 what we're going to have is the log base 2 of 9 is going to be three point one seven and this little these little brackets you see those like brackets are the floor symbol so it means we just truncate the decimal place we just truncate the decimal place and when we got one plus three so we have to have at least four levels so this is accurate we have one two three four four levels we have approximately log n levels so if you took the asymptotic complexity or the asymptotic behavior of a traversal of the heights we're going to be performing logarithmic work when we are traversing at the height of a binary structure like this if it is balanced at least if it is skewed to the right then we're going to be doing linear time work but that's another that's for another day we're going to assume we have a balanced tree structure now let's look at other implications of where we use logarithms and we'll notice them in time complexities all right so we have an array so I won't ask you the question how many times can we cut this and a half and let me give you a little help this is all you need to know to know how many times you can cut this in half until we get to what I am so why is that so why don't we start cutting it down in half so let's go one level down and cut it in half okay so now we have cut the input once we've split it in half once and now let's split these guys in half okay so now we see we are two levels deep so how much farther can we go let's split these guys in half in this level one more time so now do you see how many times could we split the original input so maybe we could use this maybe this was a helpful hint I gave you so if we take the log of this and again always base two when we're dealing with complexities implicitly so if we take log base two of eight what is the answer to that what am I asking what do I need to power two by two get eight and we can see here this is how we know how many levels we can split input this is where the logarithm came from so is this familiar does this look familiar so the thing is merge sort and quicksort run in n log n time when we don't have a specific we don't have special knowledge about a certain set of unsorted data the best we can do is n log in time with merge sort wicks orders the fast sorting algorithms so why is this in the recursion you're going to be able to split the inputs for merge sort up to log and levels of work as you can see you see all the levels of work you see we can split three times which is log of n so on each of those levels of work we do about linear work now the recurrence relation and the actual complexity gets a lot more fine-tuned than that in terms of like the exact operations we do but this is a general overview of where that comes from where that n log n comes from we have log n levels of work and we're going to be doing a certain amount of work for each level so that's why we do a multiplication against a logarithm so that's where that comes from so this is what merge sort and quicksort will do when they are partitioning the array in work shorts case we drill down to base cases and then we come back uppers with a sorted array now let's look at another example where logarithms show up all right so now here's another example we have a sorted array with the indices numbered we automatically know we can do binary search we have the invariants that if we cut the array in half at any points we will have a sorted array in both of our hands so what we can do is here we can set our bounds and let's do a binary search and see how many times we can perform a halving of the search space at maximum okay so we just set our bounds and our midpoint is going to be right there we see we hit 4 is for the value one that we're searching for it's not we overshot it since we overshot it we need to look to the left we want to go lower in value so what we're going to do is narrow the balance okay so let's take note of that so we were able to narrow our bounds one time so now let's find our new midpoint is to the number we're looking for so the thing is 2 is not the number we're looking for so we need to keep going left and we found the item what so we performed a total of two having operations to find our item K so what is the maximum operations we might have performed what if I gave you 0 is 0 in this array 0 is not in Missouri we would perform another bound reduction operation and we would have / we would have our right bound don't powder the array and at that point that would be our third check so I just said the number three where does does that look familiar does that sound like a familiar number that's in relation to this problem so if we look here three is the log of eight so again remember back to cutting things in half so that is the whole point of it we can cut in half up to three times if the item is not there the worst cases we don't find the item and our algorithm does a total of log eight narrowings of the array and that is our worst case we don't find the item and we do that many checks so that is where the logarithm shows up in binary search so the reason a logarithm is important is because the questioning asks us is very relevant to these problems where there is a halving of search base a cutting in half a certain amount of levels of a binary tree so that is where these log and things come from and if someone tells you that the solution to a problem is going to have log n complexity you should immediately be thinking maybe this is a tree traversal thing or maybe this is going to use binary search that's immediately what you should think because the only context it can have all that could ever mean in computer science Elise is a halving of the search base unless we change our base so that's all for this video if this was a clear explanation if this main things clear because this is something that used to confuse me like the video and subscribe to the channel the point of these videos is to empower software engineers to excel in the interview and that is all for this [Music]

Channel: Back To Back SWE

Views: 161,712

Keywords: logarithms, logarithmic time, logarithmic time complexities, logarithmic space complexities, logarithmic complexities, Back To Back SWE, Software Engineering, computer science, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies

Id: M4ubFru2O80

Length: 10min 23sec (623 seconds)

Published: Wed Jan 30 2019