Transcript for:
Understanding Big O Notation Basics

Big O notation is used to classify algorithms  based on how fast they grow or decline. It is   very important to understand for many types of  programming, Giorgio Thompson does a great job of   breaking down big O notation in this course. Hey,  what's up everybody and welcome to my mini series   on big O notation. And this mini series, you'll  learn everything that you need to know about big   O notation and how you can use it to improve  your ability to create efficient algorithms.   I'll use whiteboard illustrations to help you  visualize and understand concepts followed by   coding tutorials that you can follow along with  to further solidify your grasp of the concepts   will answer the question what is big O notation?  And why is it useful? So what is big O notation?   Big O notation is used to analyze the efficiency  of an algorithm as its input approaches infinity,   which means that as the size of the input to the  algorithm grows, how drastically do the space or   time requirements grow with it. For example,  let's say that we have a dentist and she takes   30 minutes to treat one patient. As her line of  patients increases, the time that it takes for her   to treat all of the patients will scale linearly  with the number of patients waiting in line.   This is because it always takes her a constant  amount of time to treat each individual patient   which is 30 minutes. This gives us a general  understanding of how long our dentist would   take to treat 10 patients 20 patients or even  100,000 patients. This is because since we   know that the dentist takes a constant amount of  time, which is 30 minutes to treat each patient,   we can always calculate the time it would take for  her to treat any number of patients by multiplying   the number of patients times 30 minutes. With this  in mind, we can categorize her efficiency as being   linear. Or as we would say in Big O terms big O  of n, where n is equal to the number of patients   the time that it takes for her to finish her  work scales linearly or proportionally with the   number of patients, we use the same technique  to determine the efficiency of algorithms,   we can get a general idea of how functions  time efficiency scales by categorizing a given   functions efficiency the same way that  we categorize the dentist's efficiency.   Let's create an easily comprehensible  function that scales similarly to the dentist.   So this function is in the same linear category  as our dentist, let's step through it and find   out why. To start the input to our function  is an array with seven items inside of it.   For each of those items, we will log this  expression which multiplies 1000 times 100,000.   Now don't let these large numbers for you, it will  always take the same amount of time to multiply   1000 times 100,000. Therefore this line of code  takes constant time. Which brings me to a very   important point, when considering the efficiency  of a function. These lines that take constant time   do not matter. Well, at least for our purposes,  they don't. This is because if our array were   some crazy length, like 200 million, changing this  expression to something simpler, like one plus one   would have a negligible effect on the efficiency  of the function as a whole, we'd still need to   iterate through 200 million items in an array.  In fact, even if the function looked like this,   we would still ignore all of these constants  and say that this function scales linearly or   is big O of n. Similarly, if we think back to  our dentist example, we see that she took 30   minutes per patient. But even if she took three  hours per patient, the amount of time it takes   her to see all of her patients will still scale  linearly. This can be difficult to grasp at first,   but it starts to make sense over time. So in the  last slide, there was a lot of talk about ignoring   the constants. But what exactly is a constant? A  constant is any step that doesn't scale with the   input to the function. For example, the time to  evaluate this expression does not change with the   input because both 101,000 are constants. That is,  these values are always the same, this expression   always results in the same value. And it always  takes the same amount of time or constant time   to return the same result. Just like we use big O  of n to describe linear functions. We also have a   big O name for constant algorithms, which is  big O of one. A good way to think about it is   every line of code is actually a function in and  of itself, which is actually true. For example,   let's reintroduce this function. So this line  of code is the reason why the entire linear func   function is O of n because as you can see as the  size of n increases the number of iterations that   the for loop must traverse increases as well. But  let's take this second line into consideration.   Let's for one second pretend that we have a  function that contains only this line. Now as you   can see, with this function, we pass in an array,  but the function does nothing with the array.   The only operation within the function is constant  because it doesn't scale with any input. So   regardless of how large of an array is passed to  this function, This line always produces the same   result. And this is the only line in the function.  So therefore, this entire function is over one.   But wait. In this function, we have multiple  lines that are over one yet we still prioritize   the line that is O of n and ignore the O of  one operations. Why is this? Well, this brings   us to our last important note, in bego, we have a  growth hierarchy, which looks something like this.   Now, don't panic, you don't need to understand all  of these just yet. So let's only pay attention to   the ones relevant to this video, or even an old  one. We'll learn about the other ones in following   videos for this series. This chart shows the  efficiency categories in order from good to bad.   That is to say that this first case of one is the  best case. And this last one is the worst case. In   big O notation, when determining the efficiency of  an algorithm, we only care about the worst case.   So that means that the worst case where the  highest order operation trumps the operations   that have better performance. So if we add the  performance of all of these lines up, like so   all of the lines of code that are o of  one get cancelled out because oh Vin is   the worst performing or highest order part of  the function. And this, ladies and gentlemen,   is why we ignore constants, because we're actually  just eliminating the non dominant items. Because   as a functions, input moves towards infinity,  constants become less and less significant.   So to recap, when evaluating an algorithms  efficiency, we must take into consideration   the efficiency of each step within the algorithm,  we then find the highest order step, or the step   that has the worst performance, and prioritize  it over all of the better performing steps,   steps that are constant, or that are over one  or as good as it gets in terms of efficiency.   So we always ignore them, unless the  entirety of the function is constant,   or o of one. And in that case, we would  categorize the entire function as constant   or o of one. And that Ladies and gentlemen,  is your answer to what is big O notation.   Okay, so to understand O of n square, we're going  to need to take the function into consideration   in the function will look something like this. So  what this function is doing is it's going to take   in a number in and it's going to iterate through  this for loop starting with the number zero   all the way up until the number in and  for every iteration of this top for loop,   we're also going to loop through this  nested for loop. And this nested for loop   is doing the exact same thing that this for loop  is doing. It's iterating through every number,   starting with zero up until the number in and  within this nested for loop, we're console logging   the coordinates for a sell within a matrix. But  to make things clear, instead of illustrating a   console log of the index i and j, I'm just going  to draw a square where these coordinates should be   for every iteration of this nested for loop. So  if it sounds confusing, just try to bear with me,   I promise it'll become clear. Okay, so let's say  for example, that we call the square function with   the number four. So that means that we're going  to iterate through this top for loop starting with   starting from zero, and then we're going to  iterate all the way up until I is no longer   less than four, once I becomes equal to four,  then we will stop the iteration. And then that's   only for this top for the for each iteration of  this actual for loop, then we're going to loop   through the entirety of this nested for loop and  do this console log. And instead of logging the   coordinates, like I said, we'll draw a square  where the coordinates would be, so you guys can   visualize this better. So let's go ahead and get  started. So for the first iteration, is going to   equal zero, and then we move on into this nested  for loop. And then we're going to iterate through   the entirety of this nested for loop. So right  now i and j are zero, so i and j are both zero.   So we're currently at the first iteration of this  for loop in the first iteration of this for loop,   and we'll draw a square and then we move up one  iteration of this for loop, so j becomes one and   we'll draw another square. And then j becomes two,  it will draw another square and then j becomes   three, and we'll draw another square and now j is  four. And since j is four, that means that j is no   longer less than n, because n is four, and j is  four, and n is four. So j, and n are now equal,   so will no longer iterate through this for loop.  So now we go back up to this for loop. And now   I is equal to one, so i is equal to one, and  j is equal to zero, so we'll draw a square and   then i is equal to one is in j is equal to one  so we'll draw a square and then i is equal to   one and j is equal to two. So draw a square and  is equal to one and j is equal to three, it will   draw a square. And now back to this top for loop  again, because j and n are now equal, we're back   up to this top for loop again, now i is equal to  two, so i is equal to two, and j is equal to zero,   so we'll draw a square and then i is equal to  two, and j is equal to one, so we'll draw a square   and i is equal to two, and j is equal to two.  So we'll draw a square and i is equal to two,   and j is equal to three, so we'll draw a square  and then now j is equal to four, which is our in,   so will no longer iterate through this nested  for loop, and we move back up to the top of this   for loop, now, i is equal to three, i is equal to  three at this point, and j is equal to zero again,   so we'll draw square is equal to three and j is  equal to one. So we'll draw a square j is equal to   two, j is equal to three. And then j is equal to  four. So we no longer iterate through this nested   for loop. And at this point, our i is now equal to  four and our n is also equal to four. And we only   iterate through this top for loop as long as r is  less than in but our eyes now equal to our in. So   now we stop iterating through this top four loop.  And what we're left with is this matrix here. And   the reason why I said that these are coordinates  for cells within a matrix is because this here   is a matrix. And these are rows. And these   are columns. So we can look  at AI, as being our column.   And then we can look at j is being row. So for  each iteration 0123 of our column, we also have an   iteration for row 0123. So coordinates being zero,  and zero, were the coordinates for this square,   and then zero and one are the coordinates for this  square, and zero, and two are the coordinates for   this square, and so on, and so forth. So what does  all this have to do with oben square? Well, hey,   just one quick interruption. If you are finding  this video helpful, or it's bringing you to some   type of understanding, please take the time  to like and subscribe. If we think about it,   this is a square matrix, that is each side will  be of the same length. And by length, I mean 1234.   This is of length four, and 1234. And this is of  length four, and to find the area of a square,   we just need to multiply the  length of one side by itself,   because every side of a square is of the  same length. So if this were a rectangle,   we would multiply the width times the height, but  for square, we can just multiply by itself because   the width and the height will be the same  length. So to get the area of this square,   we're just going to multiply four times four,   four times four. And that's going  to equal the number of cells   within this matrix, which also happens to be the  number of times that we had to perform this code,   which is four times four is 16. And four  times four is the same thing as four square.   So O of n square, our n is actually four.   And that is why typically functions with nested  for loops, like a for loop and a for loop nested   within it like this function is considered  over in square. I hope that makes sense.   Okay, so to understand all of in queue, let's take  a function into consideration. This cube function   takes in an argument in which is a number. And  it's going to iterate through this for loop and   for every iteration of this for loop is going to  iterate through the entirety of this for loop. And   for every iteration of this for loop, we will need  to iterate through the entirety of this for loop.   And I'm going to have to apologize ahead of  time for my disappointing drawing skills.   But to illustrate this, I'm actually going  to have to draw three dimensional shapes,   which is not something that I'm entirely good  at But anyways, for now, let's just ignore this   image. For now. Let's focus on this function.  So for the top level for We're going to be   iterating up until in. So  if we pass the number four   to our cube function, we'll end up here  at this first for loop. And we're going   to iterate starting from zero all the way up until  n, which is four. So let's get started. So for our   first iteration of this top level for loop, I is  going to be zero. Now for all the in cube, we're   adding in additional nested for loop. So there's  no longer just a row and a column. Now we have   rows, columns. And we also have this third  dimension here, which we'll just call height.   So we have the columns that go in this direction,  the rows that go in this direction, and the height   that go in this direction. So at this point,  we're working with a three dimensional array,   it's no longer a two dimensional array. And it's  the same concept. So it's not as difficult as it   seems, we're going to draw it out now. So we  would start with this initial for loop, and is   going to start off as zero, right. And we'll say  that this initial for loop is representative of   our columns. So we can actually go ahead and write  these numbers out just so you guys can see. So   we'll say that when I zero, this column is zero.  When I is one, we're talking about this column.   When I say two, we're talking about this column,  and one is three, we're talking about this column.   And of course, once I becomes four, we're  no longer going to iterate through this for   loop because I is then no longer less than  n, which is four, it will be equal to four.   And we can say the same thing for the rows.  So we would say that row zero would be here,   row one would be here, row two would be here,  and row three would be here. Now I apologize   if this is difficult for you to see, it's three  dimensional. So it's not really easy to draw this,   but I hope that you guys can visualize what  I'm trying to say. And then the same thing   for the height, the height would be represented by  this for loop here. So okay, and let's actually,   I'm sorry, I should, I should actually just name  these by the letter that we're using in the actual   function. So instead of calling this height,  we'll call this K. Because it's representative,   this this for loop is represented as representing  k here, so we'll just call this k as well.   And instead of calling this columns, we'll  call it AI. And instead of calling this rose,   we'll call it J. So for every iteration of this  for loop, we're going to be moving up this k   axis. So if we were to write in what the index  is for K, it's going to kind of be hard to   see right now. But it will be 012. And  three, so let's try to draw this out.   So let's do this step by step  for a little bit to get you guys   understanding what's happening. So for this first  iteration of this top level for loop, is going to   be equal to zero. So that means that I, this line,  we're going to be here at the zero index of I.   And then for this nested for loop, J is also going  to be equal to zero. So j is here. And we're going   to be at zero here. So we're still going to be  here. And for K as well, this for loop here.   This x is here, we're also going to be at zero,  which is here. So we're still going to be here.   So instead of console logging these coordinates,  we'll just draw a square for this coordinate.   So this coordinate is 00, and zero, and 00,  and zero, so we'll just draw a square here.   And again, you're going to have to excuse my poor   square drawing prowess. And since we continue with  K until K is no longer less than n, we're going to   continue to iterate through this for loop. So to  help you guys out, I can just tell, I can just   write I right now is equal to zero, J right now  is equal to zero and K. It was equal to zero,   but we just do the square for K at zero. So now K  is going to iterate it's going to increment one.   So K is now going to be equal to one. So when k  is at one, and j is at zero, and is at zero, so   i j. k is at one, then we're going to go up  another square and this is going to be kind of   hard to see because I'm literally trying to  draw three dimensional space Whereas here   and I'm just like terrible at drawing,  I'll do my best. Give that one more go.   Okay, so once we do that k increments one,  so K is now two, two is here, and then   i and j are still zero, so we're still going to  be at j here. So we're still going to be in this   section. So we'll draw another two dimensional  square here. I mean, two dimensional cube, excuse   me, if I call a cube square, that's definitely  not right cube. So there's another cube. And of   course, K is going to increment again. So then K  is going to become three. And then at three here,   we'll drill another square, I mean, cube, sorry.  And at this point, K is going to increment.   And then it's going to be equal to four. And  once k is equal to 4k is no longer less than n,   because n is also four. So now k is equal  to n. So this world is done. And now we   move up to this for loop. And this for loop will  increment one and j will then be equal to one,   because for each iteration of this for loop, we  go through the entirety of this for loop. So we've   gone through the entirety of this for loop. So  now we can move up one iteration in this for loop.   And we can't move back up to this for loop until  we iterate through everything within this for   loop. So we're still on so we're only incrementing  the row and then we're going back into iterating   K. So now that j is equal to one is still zero, so  we're still here, we're still here, because this   is the column and then I still zero, this is I and  I still had zero. And we're still here, but j went   from zero to one. So now we're here. So we're back  into k, and k is going to start off zero again.   So at I being zero, J being one  and K being zero, because zero,   okay, this is K, and this is zero.  And we're here we'll draw a square.   Sorry, once again, I said square Yeah, we'll  draw q 10k increments. We'll draw another cube.   And then k increments, and we draw another cube.   And then k increments.  Individual one more Q, because   once k reaches four, so yeah, K, okay, we'll  increment one more time, and it'll reach four.   And now K is no longer less than in. So we go back  up to RJ for loop, and that will increment one.   So this one will now become two. And it's pretty  much the same thing. Throughout the entire   throughout the entire function, and it's  getting hard to see the cubes that I'm   drawing here. But eventually, we'll  get to a point where the entire cube   is filled in, which will look something like this.   So we'll get to a point where the entirety of this  cube would be filled with these miniature cubes,   which are just the iterations of these  four loops. So once we get to that point,   and thank you cube is completely filled in. At  that point, that means that we have iterated   through the entirety of this top level for loop.  And feel free to take the time to try and draw   this out on your own. But I basically went through  as much as I could with the time that I have in   this video, but it's pretty much the same thing  until the entirety of the cube is filled. So once   all these four loops have completed, you'll  be left with the cube that looks like this.   And since this is a cube, that means that  its height, and its length, and its width,   are all going to be of the same length. And  that is to say that they're all going to be in   because if you look here we  went through in iterations of J.   We went through iterations of AI  And we went through in iterations   of K. And again, I'm sorry, for my poor drawing,  I hope that you get the idea. So if n is four,   this is going to be four, this is going  to be four, and this is going to be four.   And to get the volume of this cube, to get  the volume, the space within this cube,   since we know that all of these are going to  be the same, we only need to know one of them.   And one of them to get the volume we just do  for this case for cube, and four cubed is 64.   And that will be the volume of this cube, which  just means that there are 64 of those of these   miniature cubes within this larger cube. And  that's the volume. So O of n cubed, r n is four.   So o of four cube, which equals 64,  which is the volume of this cube.   which also happens to be the number of times  we would perform this function console log the   coordinates, but in our  case, we just do the squares.   And that is why this function is O of n cube   must first understand what a logarithm is.   Simply put a logarithm is the power that a number  needs to be raised to to get some other number.   I know that doesn't make much sense out of  context, but don't worry, I've got you covered.   Let's take the number eight into consideration.  So we want to raise some number to some power to   get a PhD. In computer science unless specified  otherwise, we can always assume that the number   that we want to raise to sum power is two. So  let's rewrite this. So we want to raise two to   some power to get eight. So this same equation  can be written like this, or this two here is   called the base. And let's not forget that  in computer science, the base is always two.   So to find the answer to this, we  just need to find the answer to this.   With that in mind, we can see that if  we raise two to the power of three,   we get the number that we're looking for  eight, so log base two of eight is three.   So with all of that in mind, let's move on to the  meaning of Oh login. For this portion, we will   be using a very bare bones recursive function to  visualize Oh login, but don't worry, I will walk   you through every step. Just stay with me. So we  will start with a number and we will use eight so   that you can easily see how this relates to our  explanation of logarithms in the previous slide.   So this variable in we will be passing to  our recursive function that looks like this.   So this functions time complexity is Oh, log  in, let's dig deeper to find out why. For now,   let's just ignore this first line and focus  on what the function is actually doing.   So when we pass a number into this function,  it divides in by two or splits it in half,   and then calls itself with the  new half or divided number.   Let's visualize this using the graph. So we first  call the function with the value eight, this   eight is then divided by two. The function then  takes the result of the division and passes it   recursively to itself as the new value for n which  in turn results in us going one level deeper.   We then do the same thing with  our new value for n which is four,   that four is divided by two resulting in a new n.  And the function then passes our new value for n   to a recursive call to itself again,  resulting in us going one more level deeper.   We then do the same thing with our  most recent value for n which is two,   we divide it by two and the function  once again recursively calls itself   at this level we will stop is we can no longer  divide in without getting fractions as the result.   Now we have arrived at the beginning of  the secret to understanding Oh login,   so watch closely. If you look at our graph, you  will see that we've gone one to three levels deep.   If you recall from our previous slide, the  log base two of eight is three. Our input   in is eight and we've gone three levels  deep. You will also notice that we have   to raise two to the power of three or multiply  Two times two times two to get eight. And since   division is just the inverse of multiplication,  we can see that when we do something like this.   So that means that this function has a time  complexity of Oh, login. Why? Because our n   is eight. And in computer science, our base  is always two. And we must have our n three   times or go three levels deep in our recursive  function to get to a point where we can no longer   reasonably have our input in, which is another way  of saying that log base two of eight equals three.   And that, ladies and gentlemen, is the secret  to understanding Oh, login time complexity.   And as a quick note, this is not only  applicable to recursive functions.   And if you're curious about that line  of code that we covered up earlier,   all it does is make sure we stopped dividing in  when n becomes one or otherwise, the function   would keep dividing fraction after fraction until  we eventually exceed the maximum call stack.   So we'll start with a very simple function, which  contains only a while loop that assigns a new   value to the variable in for each iteration. And  for this example, let's imagine that we're passing   the value eight two hour in for this function. So  that means we'll iterate through this while loop   as long as eight is greater than one. And  for each iteration of this while loop,   we're going to divide our n by two and reassign  it to n. So our n is going to be halved for each   iteration. So currently, our n is equal to  eight, because we passed in eight as in and   while n is greater than one, we're going  to iterate. So right now is eight, which   is greater than one. So we'll do this math dot  floor n divided by two for our first iteration,   which would set our n equal to eight divided by  two, which is four. And this math dot floor, all   it does is it floors the result of our division.  So for example, if we have math dot floor,   five divided by two, we would get two here,  instead of 2.5. So after this first iteration,   our in is now equal to four. So while  n is greater than one, we're going to   do another iteration. So four is greater  than one, so we're going to do this again.   And n is going to equal four divided by two,  which is going to equal two. So now our n is   equal to two. And while n is greater than one,  we're going to do this again. So in is currently   greater than one, two is greater than one. So  we're going to do it again for third iteration.   So in is going to equal two divided by two, which  is going to equal one. So at this point, our n   is equal to one. And we're going to go to this  condition here again. So while in is greater than   one, we're going to do this. But right now n is  equal to one, it's no longer greater than one. So   we're not going to continue with this while  loop. So why is this function of login,   so our n is eight. So that means  that this function should be o of log   eight. And if you remember from the previous  video on old login complexity, this is just   the same thing as o of log base two, eight, which  just means what power do we need to raise to buy   to get eight. And if we write this out, what power  do we need to raise to buy to get eight, we see   that we need to raise two to the third power to  get eight, because two times two times two equals   eight. So this three is what's important, because  division is just the inverse of multiplication.   So if we need to multiply two times two times  two to get eight, then we should also be able   to divide eight by two three times to get one. So  there's 123. So that means that for this function,   when we pass in a value for n, we're always  going to need to divide this value in By to   log in times before we can get one, which is  just another way of saying that when we pass   into this function, we're going to  iterate through this while loop,   log in iterations, before we get to the value  one. So if you see here we have one iteration,   two iterations, three iterations. So there's  three iterations here. So this is this three   is log in iterations. Because again, oh, all log  in, just means Oh, log base two of eight. Because   our n is a, n, log base two of eight is three,  because two to the power of three equals eight,   which is our n. And that is why this non  recursive function is oh log in, because   there will be log in iterations 123. Before  this while loop ends. I hope that makes sense.   To start, we should understand that in order for  binary search to work, the array that you were   searching must be an ordered array, both ascending  and descending order two arrays will work.   Let's start by visualizing our array. In practice,   this is much more useful as the size of an  array becomes much larger, but we will stick   with an array containing nine elements to  help us understand the concept more clearly.   So let's assume that we want to check our array to  see if the value 100 exists inside of the array.   The naive solution would be to iterate  through each element of the array   checking to see if the value is equal  to 100, like so. But for this method,   we have to iterate through every element in the  array up until the value that we're looking for.   What if we have to do this for an array containing  1000, or 100,000, or even a million elements.   This is where something like binary search  can be useful. So let's try this again.   So here, we're still wanting to check  to see if the value 100 is in our array.   But this time, we'll use binary  search to figure this out.   To start, we need to find the midpoint of  our array, which is just the element in the   middle of our array, our midpoint is here.  Now since our arrays in ascending order,   we know that anything to the rate of our midpoint  will be a value that is larger than our midpoint.   And everything to the left of our midpoint  will be a value that is less than our midpoint.   So we need to figure out if this number 100,   which we are searching for is greater  than or less than our midpoint.   This will tell us which side of our array our  numbers on. So if we simply write out 43 is   less than 100, we can actually see that the side  of the array that our numbers on is this side.   To paint a full picture, let's for one second  pretend that the number we are searching for is   two and not 100. In this case, two would be less  than our midpoint 43. Therefore, it will be on the   left side. And this Ladies and gentlemen, is why  binary search will only work on ordered arrays.   Because without the order, there would be no way  to tell which side the number we're searching for   is on by comparing it to the midpoint. Now let's  get back to the original number that we were   using for our example. So now that we know that  100 will be on the right side of our midpoint,   we can completely do away with anything to the  left of the midpoint including the midpoint.   So what we're left with is this,   what we've done is we've essentially cut the  array in half. To put this in perspective,   let's imagine that we have an array with 1  million elements and we divide it by two.   In just one step, we will have cut down the  number of elements that we would need to search by   500,000 elements as opposed to iterating through  all 1 million elements and searching that way.   And it doesn't stop here. We will now do the  exact same thing with this half of the array.   Let's remember that we are searching to see if the  number 100 exists within our array, we will first   need to find our midpoint. Now don't be confused  by the even number of elements in this array.   Although there won't be an even number of elements  on each side of our midpoint, it does not actually   matter because we actually just need to split  the array approximately in half. For example,   to find the mid and code we will do something  like divide the length of the array which is four   by two. That resulting to we would use as the  index of our mid. So let's write out the indexes   of this array remembering that arrays are zero  Meaning that the starting index will be zero.   And if we take this resulting two  and see what value it points to,   we see that our mid is 100, which is  the number that we are searching for.   So in that case, we would be  done, we have found our number.   But to prove that which one of these we choose  to use doesn't actually matter, let's explore   what would happen if the mid 54 were used is the  number that we're looking for greater than or less   than our mid 54. Our number is greater than 54. So  that means that we can get rid of the left side.   And what we're left with is an array  containing only two elements, which again,   is an even array. So we have no way of  determining which one we should choose as our mid   let's see, what would happen if we use 124 is  our maid is 124 greater than or less than 100.   It is greater than, so we can  ignore the right half of this array.   Now we're left with an array containing only  one element. So our so called midpoint can   only be this element. And this element is the  number we're searching for. So we're done here.   So as you can see, regardless of if you  have an auto array or an even array,   as long as it is ordered, the search for  element will be found if it exists in the array.   And that Ladies and gentlemen, is how binary  search actually works and why it is useful.   So let's just start by creating a file and we can  call it log in dot j s. For binary search to work,   the array that we're searching must  be in either ascending or descending   order. So you can't just have a randomly ordered  array and use binary search on it. So that's just   something to keep in mind throughout the rest  of this tutorial, our binary search function is   going to take in four arguments, it's going to  take in an array, and the array is just going   to contain integer values, which will need to be  ordered, so we will just do one through eight,   we'll also need to pass in the first index of our  array to the function, we'll just call it start.   And that's just going to be zero. And we will  need to take in the last index of our array,   which we'll just call end. And we can get  that by getting the length of the array   and subtracting one from it. The reason  we need to subtract one from the length of   the array is because the index is of the array  are actually zero based, but the array itself,   the length is actually not zero based, it's just  going to be the number of elements in the array.   So the array length is going to be eight, but  the last index of the array of length eight   will be seven. So that's why we subtract the one.  And then last but not least, we'll need to take in   a target value, which is the value that we're  searching for. And we're going to just search   for eight. And then we can start building our  function. And we'll just call it binary search.   And it'll take in the array  start at the end and the target.   And this function is actually going  to be a recursive function. So to   start this function off, we need to  find the middle index of our array.   So you'll notice that we're using a  built in function math dot floor here.   And the reason we're using this is  because if we go to the definition,   it says that it returns the greatest integer  less than or equal to its numeric argument,   which basically just means that if this the  division expression within our parentheses,   within our function, parentheses return something  like 5.5, the value assigned to MIT would only   be five, because we don't want to take into  consideration anything after the decimal point   because we just want to find an index, which  of course there wouldn't be an index 5.5. So   therefore, our mid would just be five. And  the next thing we would want to do is check   to see if our midpoint is actually the number  that we're searching for, which is our target.   So this would basically return true if the mid  value of our array is actually the target that   we're looking for. So we're returning true because  that means that the value that we're searching for   exists within the array, and we would be done  here. And actually, I just realized I might   actually be confusing you guys by referring to  our mid and our mid value interchangeably. So this   mid here is actually the index of our mid which  we're trying to get we're trying to get the index.   so here we can just add index as well. So when I  say our mid, I'm actually referring to the valley   So we actually want to return true if the value  that's at our mid index is equal to our target   value. So if the value at our mid index is not  equal to our target, we then want to go on to   check to see if the value at our mid index is  greater than or less than our actual target. So   actually, this should be made index.  Sorry about that. And actually,   we have another error here. So we'll start and  then target should be here. That should work.   So yeah, let's take the time to understand  what's happening in this line of code here.   So if the value at mid is greater than our target,  then that's going to mean that our target is   actually in the left side of the array. Because if  we look here, and we take into consideration that   five is going to be our mid in this situation,  in the first execution of this function,   five is going to be our mid. And if five is  greater than the number that we're searching for,   then that means number that we're searching  for is going to be in the left side,   because if five were, if the number that we're  searching for were greater than five, then it   would be in the right side of the array, because  our array is in ascending order. So this is to   check to see if the item that we're searching for  is in the left side of the array. And if it is,   what we're going to do is, we're going to pass in  our start, which is going to remain the same. So   we're going to keep the same start, which is going  to be in this case, it's going to be index zero,   and then our end is going to be mid minus one  minus one, because we're going to actually do   away with our actual current mid and actually,  well, this should be nid index as well. We only   need to assign the current mid minus one to our  in variable, because our next execution of the   function would have this as our end, and then this  as our start, and therefore we'd only be searching   1234, which we would then in turn find the mid for  1234. And then we would do the same thing. So now   what would happen if the target value that we're  searching for is greater than our mid value? Well,   let's see. So in this particular case, the target  value would be less than or mid. So that would   mean that the target value would be in on the left  side of our right. But if that were not the case,   then if our target is larger than our midpoint,  then we would do something like else return.   So we're still going to function  still going to call itself of course,   but this time, we're going to pass in the  array, the array, and instead of passing in   the original start point, we're  going to be passing in the midpoint   index plus one. And that's going to be our new  start point. And this is because we're starting   from the midpoint to the right side of the array,  because the actual value that we're looking for is   in the right side of the array, and then at  this point, our end can just stay the same,   because the end is just the end of the array. So  let's let's have a look at this again. So so let's   again, pretend that for this execution, our mid  is five and but this time, the actual value that   we're searching for is greater than our midpoint.  So that means that it can't be on this left side,   because everything on the left of our midpoint  is going to be less than because our arrays   in ascending order. So it's going to be on this  right side. And if it's greater than our midpoint,   then of course, we don't need to take five into  consideration, which is why instead of doing mid   index, and in instead of returning mid index and  end to the function, we only need to return mid   index plus one, which is going to be this index  here, it's going to be index, it's going to be   this value six at the index one index above  our actual mid. Now at this point, we're only   searching our end and our mid plus one. And we're  only searching these three elements in the array.   That's what both of these conditions cover. So  this first condition covers if the item is to the   left of our method, which is over here. And the  second one covers if the item that we're searching   for is in the right environment. And this is how  binary search works. This is why binary search   is more efficient than say linear search. Because  we don't need to check every element in the array   we can actually essentially eliminate half of  the array by knowing whether or not the item   that we're searching for is less than or greater  than The midpoint. So let's go ahead and see if   we can actually run this function and get it  to work. And I'm going to tell you right now,   we're going to try and run it twice, we're going  to try and run it searching for the actual value   that we know that's in the array. And we're going  to try and run it searching for a value that's not   in the array. And you'll see that we're missing  something in this function. So let's go ahead   and try and run it. Now to run it. Obviously, we  have to invoke the function. So we'll go binary   search. And we're going to pass in array, start  and end target. And we're going to save that.   So we will try and write it by  just using node, login dot j s.   And we broke it. Nice. Got to add in the target  here. So it caused the entire function to fail.   See it again. Okay, so let's see what  happens if we actually return the value,   I mean, console log the  return value of the function.   And we get true because eight  is found within the array. But   what you'll see here is if we search for something  that doesn't exist within the array, we're going   to break it again. So 10 does not exist. So let's  try it again. And we got maximum call stack size   exceeded, because let me show you what it means  maximum call stack size exceeded. So what we're   doing is, every time we don't meet this condition  true, we're going to call binary search again,   which is we're calling the functions recursively  calling itself again. And if we're, if we're   searching for a number that doesn't exist within  the array, binary search is basically going to   keep calling itself recursively. And there's never  going to be a point at which it stops. Even if it   doesn't find the item within the array, it's still  going to continue to recursively call itself until   eventually we reach the maximum call stack size,  which is basically you've exceeded the amount of   memory allocated to this particular application.  So to solve this issue, what we want to do is we   want to add a base condition that will stop the  function from recursively, calling itself after   it's checked the entirety of the array. So we can  do if start is greater than and then return false.   So the reason why this works is because if the  targets not in our array, it either means that   the target is larger than the largest value in  our array, or it's smaller than the smallest   value in our array. So that means our function  will keep checking our array until eventually   we get to either the largest item if the target  is larger than the largest value in the array,   or it gets to the smallest item if the target  is smaller than the smallest item in the array.   And at that point, the start and the end values  will be equal and at the point where both the   start and the end values are equal passing  our start in our into either this line,   or this line, well, in effect, make the start  greater than the end. And now we can run this   again using this tin that doesn't exist within  our array. And as you can see, we get false.   And if we even added negative here, negative  10 doesn't exist. So we get false as well.   And let's see, what else can we try. just tried to  we know two exists. And then and we get through.   So let's change this back to a to get a feel for  why this function is oh log in, let's actually   let's go ahead and create a longer array here.  So currently, our array only contains these eight   elements. And it's going to be kind of hard to get  a general understanding of the way that our input   scales with such a small array, so we can go ahead  and just just empty out our array, and we'll just   create our own array. So let's see, the trade our  own array we can just do for i equal zero, i is   less than 1024 i plus plus. And then here  for each iteration of AI, we can just do   grade up, push high. And let's  think let's actually make eye one.   And then we'll make this less than  or equal to. And then after that   we can console. log our array. And for now,  let's just comment this out. And let's see.   Okay, so at this point, we have a longer  array, which will hopefully help for you   guys to visualize how the input is scaling when I  do some console log trickery here. So yeah, so we   don't need to log this anymore. Just delete that,  actually. So we're creating a new array here.   And it's going to be an array that has elements  from one to 1024. And for the purposes of this   example, I don't want us to find the element,  I mean, the item in the array, so we're just   going to change this to something that doesn't  exist within the array. So we'll just put it like   that 100,000 does not exist within our array,  and also the end, and this is getting the end   from this current array. So we're going to need to  bring this down to after we create our full array.   So this array is empty here, and then we're  adding all of the values in this for loop and   then we get the end of the array. And the start,  of course, can still be zero because it's zero.   And also, we can go down here and delete till  the, we don't need to console log this anymore,   because we're going to do another  console log. So we're going to   execute the function here. And then here is where  we're going to try and make some magic happen.   So for each call to binary search, like each  recursive call, we want to not just recursive   call the first call for the first call. And each  recursive call, we want to log with the array   that we're searching through is looking like.  So in the beginning, it's the full array,   which we just showed when we console logged in  earlier. And then at each call to the function,   the rate is going to essentially be halved. So  it's going to look something like let's see,   console dot log will do array dot slice.  And we're going to do the start and the end.   So what that does is, it's only going to show  the parts of the race from the start to the end,   it's not going to show the full array  anymore. And let's see if that works.   so here we can do node, log in. Okay, and yeah,  that worked. So maybe I can make this smaller.   So you can see, so when I make it smaller like  this, it's kind of easy for you to see like,   well, at this point there is too long to show its  entirety. But you can still see what's happening   here. So like since the value is greater than  the left side of the array, you can see that   all these lower values are going to essentially  be eliminated, and it continues to get halved   and have an halved. And here's where you  can start to see visually what's happening   here like I can see that it's the ray is  continuing to get smaller and smaller.   To understand ovan login, we will take  this small function into consideration.   This function has a complexity of ovan login.  Let's step through this code line by line so   that we may understand what is happening here.  This function takes one argument in which for the   sake of this example will be for we then declare  another variable y which we will set equal to n,   we will get to what this variable  Y is for later. And at this point,   we have a while loop that iterates through n until  n is equal to one. For every iteration through   in this code within the while loop is run. Let's  visualize this. For the first iteration of the   while loop in starts off is four but we divide it  by two, so n is now equal to two. Then we get to   this line of code which is the start of a for  loop. This is where this variable y comes in.   The reason we declared this variable before  the start of the loop is because n is getting   divided by two for each iteration. This in  turn is reducing the size of the variable n.   But for this inner for loop we needed to iterate  through the original size of our original n.   So we stored the original end in a separate  variable. Okay, back to this inner for loop.   For each iteration of this for loop up until the  size of n we will log or print the value for I.   Once this is finished, we move on to the next  iteration of the while loop and repeat the process   going into this iteration In is now two, we  start by dividing in by two. So n is now one.   And once again, we iterate through our  inner for loop up until the size of y.   Now at this point, you will notice that our  n is now one. If we check the condition of   our while loop, we see that we only want to  iterate while n is greater than one. So the   while loop will now terminate, and the function  is finished. Now, after all is said and done,   and with everything written out, we can  see that there's a top level loop here.   And there's an inner loop for each  iteration of the top level loop.   So this is where the magic happens. So pay  close attention. For every iteration through   the top level loop, which iterates  until n is one in is divided by two.   This means that this top level loop never actually  iterates through the full size of our input   in the value for n is being split in half for each  iteration, which is why we would say that this top   level loop has a complexity of Oh login. If you  are confused about why this top level loop is Oh,   log in, let's take some time to prove it by  writing it out. So this is Oh, log in. Let's plug   in some numbers. Now if you've watched my video  on Oh, log in, you know that in computer science,   the base of a logarithm is always two unless  stated otherwise. So this can be rewritten as log   base two of four, four, because we're replacing  in with our actual input for n, which is four. And   log base two of four is two, because you need  to raise two to the power of two to get four.   And as you can see, this makes sense, because for  this top level loop, we only iterate two times.   So for this top level loop, we have log base two  of four equals two. Now we need to take a look at   what is happening in each of the two iterations  of the top level loop. For each iteration,   we loop through the full size of y, which is  the original size of n. So that means that   each of these inner loops has a complexity of  O of n, which just means that processing time   increases linearly with the size of n. Now  this is where we bring everything together.   O of n log in really just  means O of n times log in.   And if we plug in some numbers here, we get this.  Because remember, log base two of four equals two.   And if you look at our visualization, it makes  perfect sense, because for each iteration of the   top loop, we iterate through the entirety  of y, which is our original value for n.   And that, ladies and gentlemen, is  how you visualize all of in log in.   So we can start by creating a file,  let's just call it merge sort,   well then create a function,  which will also call merge sort.   The argument to this function is going to  be the array that we're looking to sort   for the first portion of this function,   we'll need to make sure that the array that  we're passing in has a length greater than one,   we will need to do this because if the array  is only if length one and there's only one   element in the array, then it is already  sorted. This will also be our base case,   as this merge sort function is going to be  a recursive function. Next, we're going to   need to split our array in half. To do this, we'll  first need to find the middle index of our array.   So with this math dot floor here does is it makes  sure that we only take into consideration the base   number from the result of the division. So for  example, if we divide a number that results in   I don't know, let's say 5.5, we wouldn't take  into consideration the number after the decimal   point. So we would only return to the variable  the number five. And this is because when taking   indexes into consideration, there is no index 5.5  or 2.2 or 1.1, there would only be an index one,   five or two. So this is why we're using math dot  floor here. And once we have the middle index of   our inputted array, we can then split the array in  half and create a separate array for the left side   and a separate array for the right side. So we can  do that by just creating a new array left array,   and then we can set left array equal to the input  array dot slice, and then the indexes are going to   be the arguments that we passed. So basically  slices from and to. So we want to slice from   the first index of our input array. And we want  to slice up until the middle index that we just   that we just got. And that's because we want the  left side of the array. So let's say for example,   the array looked like this. And we win, we went  ahead and got our middle index, which would be   something like this three here. And then we want  to create an array starting from this zero index,   up until our middle index, which  would be the left half of the array,   and then we would go ahead and do the same  thing for the right half of the array.   So we're going to actually go ahead  and do the same thing for the right   half of the array, we'll just call it right array.  And we'll do array dot slice again. But this time,   we're just going to do from the middle index  all the way until the index, the last index   of the array, and the way we get the last index  of the array is just by using array dot length.   And this here can actually be a bit confusing,  because we know that array dot length gives us   the length of the array, which is the number of  elements in the array. And we also know that array   index is zero based. So basically, if the length  of an array is five, there will only be index   0123, and four, there won't be an index five. So  here, you might be wondering how this is actually   working. And it's because actually, there's an  error. And this method method is not slicers, just   slice, but it's because this slice method slices  up to in but not including in. So basically this   end value, it's not included in the actual array,  slice, only the value before will be included.   So for example, if we have an array  that looks like that looks like this,   the end that we would use for this array would  be three, even though that there's only index 01.   And two, it will slice up until end not including  in so this is why we don't need to subtract a one   from this because if we were to subtract one from  array dot length, and use that as the last index,   or the end index that is passed to the slice  method, then we actually wouldn't get the   full array, we would only get up until this  one, but not including this one. So they were   able to only look like this in this slice. I  hope that makes sense. It's a bit confusing.   And also keep in mind that with this example  I just gave above, I'm actually not taking the   middle index into consideration. So for this  array, in particular, it would look something   like array dot slice, well, slice and there will  be zero index up until array dot length minus one.   Anyways, last but not least, for our actual emerge  cert function, what we're going to need to do   is implement the recursive portion of the  function, which is we're going to return   and bear with me, we're going to return a  helper function that we haven't created yet.   And we're going to call it merge. And  within this marriage helper function,   we're going to accept two parameters, which  is going to be the left array and the right   array. And what we're going to pass to merge is  going to be the recursive call to merge sort.   And then our left array, and we're also going to  pass in the recursive call to merge sort, and our   right array. This is going to seem a bit confusing  right now. But just bear with me, I will explain   how this is working. And I will try to make things  clear for you. But for now, we don't actually have   this merge function, so we need to go ahead and  create it. So let's go down here and create this   new helper function called marriage, which will  take in the left array, and the right array.   Oh, sorry, and it's not merger, it's merge. Now  this function is going to be the function that   actually merges the two arrays. So the way that  Merge Sort works is we use a divide and conquer   approach in which the input array is basically  halved until we have in arrays of length one, and   at that point, arrays of length one, as mentioned  above, when we created this space case, here,   an array of length one is already sorted. So to  visualize this, if we have an array, that is one,   there's only one element in this array, so  obviously, this one is going to be the first and   last element in the array. So there's no need to  sort it because there's nothing to compare it to   with. What we do in this actual merge function is  we're going to bring these sorted arrays together   and compare them and then sort those individual  one element arrays. So one thing to keep in mind   throughout the process of writing this merge  function is that this merge function is always   going to take in two already ordered arrays,  starting with the ordered arrays of length one.   So to start, we're going to To create a variable,  which is going to just be the result array,   and it's going to start off as an empty  array. So these all equals just an empty   array. And we're also going to define our base  indexes for the left array and the right array,   but could index equal zero. Now  we'll do the same thing for right.   Next, we'll create a while loop that's going  to compare the two arrays element by element.   And actually stick here, this  length. So within this while loop,   we're going to compare each element of both  arrays and whichever element is less than   the other will get added to the result array  will then increment the index of whichever   element got added to the result array because  that element no longer needs to be compared.   If you're a bit confused by this, just  bear with me, I'll actually create an   illustration for you to understand it better.  But for now, let's just write out the code.   Let's imagine that the rays that we want merged  look like this for the left array and this for   the right array. Now keep in mind that the  merge helper function merges ordered arrays,   so it will not work on unordered arrays. In  this example, we are merging two ordered arrays   of length three to show the entirety of the  functions functionality, but this will also   work for naturally sorted arrays of length one. So  for this while loop to continue, both left index   and right index need to be less than the length  of their corresponding arrays. As you can see,   these indexes are incremented, every time that  index is element is pushed to the result array.   So if we draw this out, it looks something  like this. Here are the two arrays and their   indexes. In this next line, we check to  see if the element at the left array index,   which is currently zero is less than the element  at the right right index, which is also zero.   So it's three less than one. No. So that means we  do what's in our else condition, which is push the   right array element at its current index to the  result array and increment the right array index.   And now our right array index  is one so we can move this.   And then once again, we do our comparison at  the top of the for loop is three less than   six? Yes. So we push three onto our result  array and increment our left array index.   And we can move this over as well. And  back to the top of our for loop again,   is 12 less than six? No. So we're going to  use the code in our else condition, which is   push the right array element six to the result  array and increment the right index. And again,   we will move this and now is 12 less than 15.  Yes, so we push the 12 from the left array to   the result array and then increment the left index  as well as move this arrow to the new left index.   Now is 16 less than 15? No. So we move on  to our else condition and push the 15 from   the right array to our result array  and increment the right index by one.   Now at this point, this while loop will terminate  because if you remember this while loop will only   continue if the left index is less than the  left arrays length, and the right index is less   than the right arrays length. At this point, our  right index is equal to the right arrays length.   As you've probably already noticed, there's  still a 16 left in the left array that has   not yet been pushed to the result array. But the  while loop is already complete. So what do we do?   After the while loop, we're going to add  another line of code that looks like this.   So this return is going to return a single  array that is a combination or concatenation   of three arrays the result array, a slice of  the left array and a slice of the right array.   So this slice function if we  only pass one index to it,   it will be used as the start of the slice and  will slice up until the end of the array. Let's   break this down. So if you remember from the last  slide, our result array currently looks like this.   And we're going to add to it a slice from  the left array starting from the left   index that we incremented which is two which  results in array containing only this part   And we're going to add to that a slice of the  right array starting from the right index that   we incremented, which is three, which results in  an empty array, because index three would be here.   And with all of those combined, the result being  returned is an ordered array that looks like this.   Now let's go ahead and add in the return  that we just discussed in the illustration.   And this completes our merge function. And  now that the merge function is complete,   our merge sort function is also complete. And now  we can go ahead and test this out. To test this,   we will need to create an array. And this array,  we will need to pass to our merge sort function.   And there you have it, our sorted array.  And if we take the time to go back in here   and have a look at the code, you'll see that  within this merge sort function, we're dividing   the input array into recursively, which makes  this Merge Sort portion of the function of log in.   And actually, this merge function is  all event because it needs to touch   every element within both arrays to actually sort  them. So with this merge function being old in   and the actual recursive merge  sort function being of login.   For every level up until the depth of this  recursive function, we're actually going to be   doing this merge, which is O of n. So  to get the overall time complexity,   we would just have to multiply the depth  of this recursive function by O of n,   which is O of n log in because of N log N  is just multiplying in by log in and log in,   in this case will be the depth at which  this recursive function needs to traverse.   So let's visualize this merge sort function, we'll  go through the code line by line. So let's imagine   that we have an array that looks like this. So  this array here will be our input array. So this   is the array that we're going to pass to our merge  sort function here. So this array is this array.   So the first portion of the code here, it just  checks to see if our array is greater than length   one, because an array of length one is already  sorted. So if we get an array of length one here,   we're just going to return that array  as an already sorted array. But if the   array is greater than length one, then we're  going to move on to this portion of the code.   And this portion of the code is where the divide  and conquer approach is implemented. So basically,   here, we're going to split our input array.  By getting the middle index of the array,   we're going to split it into two separate  arrays, which will look something like this.   And these individual arrays  left array and right array.   After their split, they're going to be once  again passed to the merge sort function.   Once again, we end up at this portion of the code,   because this array and this array are individually  being passed to this merge sort function.   So for each of these, we end up at this portion  of the code. And both of these arrays are   not less than length do, we have an array of  length two, and we have an array of length three.   So they're going to move on to this portion of  the code in which we use the divide and conquer   approach once again. And let's go ahead and write  that in here actually, because it's important.   So once again, we're going to  get the middle index of our array   and create a left right and a right array by  splitting the single array on its middle index.   So you will notice that this array, this array and  this array are already of length one. And as, as   we've seen here, we're going to pass these arrays  of length one to merge sort, we're going to pass   these arrays in to merge sort, and then they're  going to get to this conditional, and they're less   than length two. So we're just going to return  these rays. So for these arrays, we can stop.   But this right here is of  length two. So this array   is going to get to this portion of the  code again, and we're going to split it.   And now, these arrays are of length  one, so we can stop here as well.   So these calls to merge sort, are the same  as these calls to merge sort. But we still   haven't called merge. And what merge is  going to do is it's going to take two   already sorted arrays, and it's going to merge  them together into one single sorted array.   And what that's going to look like  is, it's going to be called here,   these results are going to be merged together  into one sorted array. So these two sorted arrays   are going to be combined and returned  here as a sorted array of length two.   And the same thing will be done  here. We're going to merge.   And these two sorted arrays are going  to be combined and returned here   as a single sorted array.   And we'll do the same here. Merge. And these  two sorted arrays are going to be combined   and returned here as a single sorted array. And  last but not least, we're going to merge here.   And these two sorted arrays  are going to be combined   and returned here as a single sorted array.   And let's not forget our  initial call to merge sort.   So that's how we can visualize  recursive merge sort.   But you're probably still wondering what  this merge function is actually doing.   So as mentioned before, this merge function  takes two already sorted arrays, and it   combines them together into one sorted array.  And that function looks something like this.   So as you can see, merge takes  in a left array and right array,   both of which are sorted, and then it will return  this result array, which is a combination of both   the left array and the right array sorted. So to  understand the time complexity of merge store,   we'll take a array and array of  length four into consideration.   So this input array will pass  to the merge sort function.   And what that call to merge sort will do  is divide the array approximately in half   and those halves will be passed  to merge sort recursively   at this point, We have our arrays of length one.  So we can't split these rays any further. And to   understand the time complexity of merge sort, we  need to understand, oh, log in. So as we know,   in computer science, so log in is the same as log,  base two in, and in this case, in is the length of   our array here, which is four. So in the  reason you need to understand login, is because   this divide and conquer approach that we're  implementing here is login. That is to say that   log base two, a four, which is our in our  n is four equals two. And that's because   two to the power of two equals four, which means  that for an array of length four, there will be   two levels to our recursive tree structure.  And we can see that here, you have level one,   and we have level two. So this is a level, and  this is a level. And for each one of these levels,   what we need to do is we need to touch every  element of n, because we need to sort them.   And in order to sort them, if you  remember from our illustration of merge,   within this merge function, the while loop within  this merge function, needs to touch each element   to compare the elements and create the merged  array. So that means that for each level,   we need to merge. And this merge function  needs to touch every element of n.   So that means that each  level is actually Oh, then.   And there are log n levels. So O of n times  log in really just means Oh, of four, because   four is our in, in is for 1234. So four is our n  times log, base two, a four. And as we seen here,   log base two, a four is actually just two times  four. So the number of elements in the array,   and the number of levels that we need to traverse,  so for every level, we need to touch in elements   in the array, which is two times four. And that's  why mergesort has a complexity of O of n log in.   So we'll start by examining this recursive  implementation of Fibonacci. So let's imagine   that we pass the number four to our fib function.  So at this point four is our value for n.   So after we call this function, we'll end up  at our first if block. And this if block just   returns zero if n equals zero, and then we move  on to a second if block in the second if block   just returns one if n equals one. So once  we pass the number four into our function,   we'll end up at this first if block. And both  of these if blocks are base cases, because   as we know, with recursive functions, we need  to have a base case so that the function doesn't   continue to call itself even after we're finished.  So we pass the four into our fib function,   and four is not equal to zero, so we don't  return zero, and four is not equal to one,   so we don't return one. So we end up here. And  what this return does is it adds together the   result of two more calls to the Fibonacci  function, this first Fibonacci function,   we're going to call with our n minus one, so four  minus one, and the second one, we're going to   call with our n minus two, so four minus two.  So let's have a look at what that looks like.   And as we can see, four minus one is just  equal to three, so this would actually just be   three. And same for here. This would  just be equal to two. So at this point,   we have to call to our favorite our Fibonacci  function. One which we're passing three is our in   and one numerator passing two is our in. So for  both of these calls, neither one of these will   Return at these IP blocks. So we'll end up back  down here again, which will look like this.   And again, we can just do  the math in the parentheses.   And let me just make this a little bit smaller.  So at this point for these three calls to the   Fibonacci function, we're going to reach our  base case, because we're passing zero for this   call. And we're going to just return zero at  that point. And we're passing one for these   two calls. And we're going to just return one at  those points. So these are going to be complete.   These ones are done. And for this function we're  passing to is our n, which isn't equal to zero   and is equal to one. So at this point, we'll  then again go down to this portion of the code.   And now these two have reached our base cases as  well. And one more time, I'll need to shrink this.   So now we'll get into the reason why  this recursive Fibonacci function is   an exponential function. First, let's start  by observing this recursive tree structure.   So as we can see, here, we have one, two and  three levels to this recursive tree structure.   So we can write that out level one, level two,  and level three. And for this first level, here,   we're calling the fib function two times.  So one, two, and for this second level,   we call our fib function four times 1234. So  this level, we make two calls to the Fibonacci   function in this level, we make four calls to  the Fibonacci function. And let's just ignore   this third level for now. And let's just focus on  these top two levels. So two here is the same as   two to the power of one and four, here's the same  as two to the power of two. And as you can see,   our exponents correlate with our levels. So  actually, if these three functions were to make   their two additional calls to recursive Fibonacci,  we would have something that looks like this. So   we have two calls here, two calls here, and  two calls here. So we'll just write this out.   So let's imagine that these are also additional  costs to the recursive Fibonacci function. And   let's just imagine that that's the case  for one second, just so that we can get   a better understanding of why this function  is of exponential time complexity. So now,   if we count the calls at this third level  to our recursive Fibonacci function,   and keep in mind that these calls won't actually  be made, only these ones will be made. But we're   just writing this out so that we can get a better  visualization of what's happening here. So if we   counted out these calls to the Fibonacci function,  it would be 12345678. So we would have eight calls   at this third level, and eight is the same as two  cube or two to the power of three. And as you see,   once again, our exponent corresponds with our  level. So that means that if our n is four,   we would go three levels deep. And at each level,  the number of calls to our Fibonacci function   increases exponentially. But you might be  wondering, since our n is four, and we stop   here, when it's two to the power of three,  as opposed to two to the power of four,   how does that result in this function being off to  to the end? Well, it's actually quite simple. So   in actuality, this Fibonacci function is O of  two to the n minus one. And if we write this out,   you can see it's o of two to the fourth  power minus one, which is just equal to O of   two to the third power, which is the same as  the number of calls made at this third level,   right. And if you remember, in bego, we ignore  constants. So if in actuality, this function is   O of two to the nth power minus one, and we  ignore the constants, that means that we're   going to ignore this minus one, which results  in the time complexity of this function being   o of two to the N. And at this point, you're  probably wondering how we're able to add these   function calls in here. And in actuality, I only  added these function calls in here to give you   guys a better visualization of what's happening at  each level and why we're considering this function   to be off to to the internet. Because it's easier  to visualize if we actually write out these   functions that we're actually not calling. And we  can do that because with bego, as we've learned,   we're only looking for an upper bound, like we're  not looking for a tight bound, we're not looking   to be very specific, we're only looking for you  can say an estimation of the worst case scenario.   So as you can see here, on this left function,  we're calling fib and then we're subtracting one   from n. And on this right one, we're calling  fib and then we're subtracting two from n.   So this right side of the tree is always going  to be shorter than this left side of the tree,   there's always going to be this empty space.  Because on this right side of the tree,   at every level, we're subtracting  two. And at this upside of the tree,   at every level, we're subtracting one. But  when we're taking bego into consideration,   we don't need to worry about this. And regardless  of what number we pass into this function,   at the bottom most level, there's always going  to be a gap on this right side. But that's okay,   because we're only looking for an upper bound.  So these are just here to help you visualize what   is actually happening and why this function is  considered to be of exponential growth. And that   is why recursive Fibonacci is of exponential  time complexity, I hope that makes sense.   We'll start with the function that will call F.  And this function will be a recursive function.   So this first portion of the code is going  to be our base case. So if the value for n   pass to this function is equal to zero,  then we're going to print these stars.   And then we're just going to return but if we  pass a value to n, that's not equal to zero, then   we will go down here to this for loop. So let's  start with an example. So let's say that we pass   the number three to our function, what will happen  first is we'll check to see if in which is three   in our case is equal to zero, which it's not. And  then we'll move on to this for loop. And what this   for loop is going to do is, for every iteration  of in, for every iteration, up until three   from zero up until three, which is our end, we're  going to recursively call this function again,   this time using our n minus one. So let's, let's  try to visualize this. So if we pass through to   this function, and we end up at this for loop,  we can write it out like this. So for each index,   up until three, but not including 3012. And the  reason we're only doing for each index 012 is   because here, I starts off at zero, and we're  going to iterate through our input value in   up until AI is no longer less than in. So  once I becomes equal to n, then we'll stop.   So if I were to be three, then we wouldn't go  through this loop again. So that's why it's 012.   And for each of these iterations, 012,  we're going to call this function again.   And that's going to look something like this.   So if you look here, we're subtracting one  from in that we're passing to the function   at each iteration of this for loop. So  if n is three here, for each of these,   n is going to be equal to two because we're  going to subtract a one for each of these.   So these are actually going to be f two. And for  each of these, we're going to do the same thing   that we did for the first call to  this function to this f function.   But this time, we'll only iterate  through indexes, zero, and one.   So each of these are their own individual calls to  this recursive function, right. And each of these   needs to have their own for loop, which  is this, this in this. So at this point,   f is two. So we're iterating up until I  is no longer less than two. So we'll have   index zero and one that we're iterating through  and for index zero and one, we're going to do   this and the same for this call to the recursive  function for index zero and one or We're going   to do this and the same for this one. And I  apologize if the writing here is getting too   small. But you'll see that this recursive tree  gets very large very quickly. So I'll actually   need to shrink this down a little bit. So that  we can have more room. So for each of these,   we're going to call the recursive  function again. But this time,   the function is being called with two minus one,  which is going to mean that our in is going to be   one. Let's make this a little  bit smaller, actually. And again,   I apologize. So at this point, our for each  is only going to happen once for index zero.   Man, this is getting really tiny.   Okay, so at this point, our F is one for all  of these calls to the recursive function,   and AI starts off as zero. And as long as i  is less than n, which is one, then we'll do   this code. And it's only going to be less than  in when it's zero, which is this one iteration.   So for each of these calls to the recursive  function, we're only going to call this function   once for this first iteration, which is zero. Now  at this point, it's going to be f one minus one.   And f one minus one is actually going to be  equal to zero. So it's going to be f zero.   So we're going to be passing  zero as our in to the function.   And it's going to be a little bit difficult to see  because it's small. But if we remember up here,   in the actual function, our base  case is if n is equal to zero,   then we're just going to console  log, and then we're going to return.   So for each one of these calls to the recursive  function, we're going to perform this code this   console log code. And then after we perform  this console log code, we're going to return   so it's going to be finished, this entire  function will be finished, because all of   these are going to return, they're going to  log the code, and then they're going to return.   And once all of these return, this entire function  is going to be complete, it's going to terminate.   So instead of writing out console log, we'll just  write that each of these functions performs log   n after the log, the function  will return. So it'll stop.   So for the last time, I'm going to need to make  this a little bit smaller. Alright, so what   we're left with when this function is finished  is we're left with this tree structure. And   this tree structure shows how many recursive  calls that we had to make to get to our base   case for each of these recursive calls. And if you  look here, I'll go ahead and circle these so that   you can see them more clearly. If you look here,  for each of these recursive calls to the function,   we had to perform this code, we  had to perform this code here   for each of these recursive calls to the function.  So at the final level, where our base case was,   we had to perform this code. And if you count  these, you'll see that this is 123456. So six   times we needed to perform this code passing three  into our function caused us to need to recall this   final recursive call to our function six times and  perform this code six times. And that number six   is our key to understanding factorial  time complexity, because if you look   here, we have oh three factorial. And the reason  why is because our n is three, right? So it's,   we're just substituting so all three factorial  right and three factors. Mario is six actually,   because to get the factorial of a number, you  just multiply every number up until that number.   And if we multiply two times one, we get  two. And if we multiply that two times three,   we get six. And, and again, we needed to execute  this console log this code, we need to execute   123456 times. And if we dig a little deeper, we'll  see the three factorial is a result of multiplying   every number up until three, which is also the  same as multiplying every number from three down   until one, which we can see if we look at how it  progresses through our tree structure. Here, we   can see the first three is passed. So first three  is passed. And then three times two is passed   three times. So times three times two is best.  And the result of three times two is six,   and six times six times one is past. So six  times 123456 times one is past. So this for   loop first passes to three times, so passes  to three times 123, which is the same as 333,   times times two, three times 123, passing two.  And when we've asked to to the function, we do   two iterations, so three times two  iterations. So we're going to do this,   we're going to iterate through this for loop of  two iterations, three times three times two, and   then three times two is going to be six, because  we do two iterations for each of these three.   So this, these iterations plus these iterations,  plus these iterations equals six iterations. And   for each of these six iterations, we're  going to pass one to the function, so six   iterations, so six times will pass one to  the function. So that's here, six times one,   six times one, and that is factorial  time complexity. I hope that makes sense.   So to understand space complexity, we'll  take this function into consideration.   And this is a recursive function, that basically  just returns a call to itself with its input in   minus one, it's going to do this until  we reach a base case where n equals zero,   and then it's going to just return and at that  point, this function will be complete. So let's go   ahead and draw with the execution of this function  would look like. So let's say that we passed the   number five to this countdown function. So with  this first call to countdown with argument five,   we'll end up at this base case. And we'll see  that our n five is not equal to zero. So we'll   move on to this part of the code, which is just  calling this function again with five minus one.   And of course, five minus one is going to  be four. And once again, we'll end up here,   and we'll call the function  again with four minus one.   And we'll continue to do this until we  pass zero as our end to the function.   And I will need to make this a little bit smaller.   And finally, we get to the call where we're  passing zero as our into the function.   At this point, if n is equal to  zero, that function will just return.   So to understand space complexity, it's actually  quite simple. So since this is a recursive   function, each one of these calls exists on the  call stack simultaneously. So that means that if   we call our countdown function with five, it's  going to then call itself with four and at this   point, this initial call still exists on the call  stack. And the same for when we call three. These   two calls still exist on the call stack, and all  the way down until we reach our base case. Every   single one of these calls still exists on the call  stack. And each one of these calls takes memory.   So each one of these calls existing on the stack,  they take up memory. And this is how we come to   an understanding of space complexity using this  recursive function as an example, because if we're   returning at this point, when we reach our base  case, that means that it means that we have 123455   calls taking up space on our call stack, and five  also happens to be our value for n. So that would   mean that this function, its space complexity is  O of n. So this function has a space complexity   of obon. So the most important thing to remember  here is that all of these recursive calls exist   on the call stack simultaneously. And each one of  them takes up memory, which is why, if we have,   if we pass in five, two as our n, we'll have  five calls existing in memory simultaneously,   which means that our space complexity is going  to be over then it's going to scale linearly with   the size of the input. So if we increase the size  of this input, the space required to execute this   function is going to scale proportionally with  the size of this input. So now that we have an   understanding of space complexity, we can get into  some common mistakes that people make with Bingo.   And the first one being that when you first  start out with Viggo, you might see a function   that looks like this that has two for loops. And  you might instinctively assume that this function   is of all of in square time complexity, because  you see that there are two for loops here. So   that must mean observe in square. But actually,  as we've learned O of n square actually means   that for each iteration, up until the size of our  input, we're going to iterate all the way through   an additional for loop up until the size of  our input. So what does it mean if we have   two for loops that aren't nested that aren't old  in square, it's actually quite simple. So we have   one for loop here, and we have another  for loop here. And as we already know,   this for loop would be O of n, time complexity.  And this one would also be O of n. So this point,   we have to all events, so that could easily be  translated to o of two in, which is just all   of two times in so two times we have all of in.  But if we remember from our previous lessons, we   ignore constants. And in this case, multiplying in  by two, two is just a constant. So we can actually   just drop this constant, in which case, this just  becomes over then. But there's one important thing   that we need to recognize here. This is all then  because we're iterating through the same input for   both of these four loops. So as long as our loops  are acting on the same input, then this would be   the resulting complexity. But there's actually  another common mistake that people make when   taking time complexity into consideration,  which is somewhat related to this mistake.   And this common mistake involves having  two separate inputs to the function.   So let's first take this two inputs add function  into consideration. So if you remember from our   last example, we only had an input, we only had  one input, which was a and the two for loops loop   through that same input. But for this one, you can  see that we have two separate inputs here. So we   have an input a, which is loop through in this top  four loop. And we have an input B, which is looped   through in this second for loop. And some people  might make the mistake of thinking that this   is the same as the last situation where the result  would be o of two in. But this is actually wrong.   Because in this particular situation, we have no  way of knowing the difference in size of both of   these inputs, like all we know is that these are  two separate inputs. So these two separate inputs   could be of either completely different sizes,  or they could be of the same size. But from our   analysis perspective, we have no idea. so in this  situation, when we have two inputs, and we have a   separate for loop for each input, we're going  to need to keep track of both of the inputs.   So in this case, the time that it would take to  loop through both these for loops is O of A plus   B, because we need to first loop through this one  up until we reach the value of a and then we need   to loop through this one up until we reach the  value of V of B and at this point, this can't   be simplified any further we need to acknowledge  the fact that both of these inputs are separate   inputs. So this would be over a plus b. And here  we have the similar situation where we have two   inputs, but this Time The four loops are nested.  And a lot of people make the mistake of saying   that this a function that looks like this is O  of n square. But that would actually be wrong as   well, because what does O of n square mean over  n square means that for every iteration of one   input, we're going to iterate through that  same exact input. But in this situation,   when we have a, we have two separate inputs. For  every iteration of one of the inputs, we're going   to iterate through the other input. So what that  means is, this is wrong. In actuality, it's o of A   times V, because again, we need to  specify that these are two different   inputs. And these inputs could be of  different sizes. And we need to make   that visible when we take our complexity into  consideration. So that is space complexity   and some common mistakes that people make with  big O notation. I hope that that makes sense.