Time Complexity – Big O Notation Course

Big O notation is an important tools for computer scientists to analyze the cost of an algorithm. Most software engineers should have an understanding of it.

We just published a course on the freeCodeCamp.org YouTube channel that will help you understand Big O Notation.

Georgio Tunson, aka selikapro, created this course. He does a great job explaining the complex concepts with diagrams and code.

Big O notation is a way to describe how long an algorithm takes to run or how much memory is used by an algorithm.

Here are the sections covered in this course:

• What Is Big O?
• O(n^2) Explanation
• O(n^3) Explanation
• O(log n) Explanation Recursive
• O(log n) Explanation Iterative
• O(log n) What Is Binary Search?
• O(log n) Coding Binary Search
• O(n log n) Explanation
• O(n log n) Coding Merge Sort
• O(n log n) Merge Sort Complexity Deep Dive
• O(2^n) Explanation With Fibonacci
• O(n!) Explanation
• Space Complexity & Common Mistakes

Watch the full course below or on the freeCodeCamp.org YouTube channel (2-hour watch).

Transcript

(autogenerated)

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.