all right now that we were done with abstract data types we need to have a quick look at the wild world of computational complexity to understand the performance that our data structures are providing so as programmers we often find ourselves asking the same two questions over and over and over again that is how much time does this algorithm need to finish and and also how much space does this algorithm need for my computation so if your program takes a lifetime of the universe to finish then it's no good similarly if your program runs in constant time but requires a space equal to the sum of all the bytes of all the files on the internet internet your algorithm is also useless so to standardize a way of talking about how much time and how much space is required for an algorithm to run theoretical computer scientists have invented Big O notation amongst other things like big Theta big Omega and so on but we're interested in Big O because it tells us about the worst case Big O notation only cares about the worst case so if your algorithm sorts numbers imagine the input is the worst possible arrangement of numbers for your particular sorting algorithm or as a concrete example suppose you have an unordered list of unique numbers and you're searching for the number seven or the position where seven occurs in your list then the worst case isn't when seven is at the beginning or in the middle of the list it's when seven is the very last element of the list for that particular example the time complexity would be linear with respect to the number of elements in the size of your list because you have to Traverse every single element until you find seven the same concept applies to space um you could just consider the worst possible amount of space your algorithm is going to need for that particular input there's also the fact that Big O really only cares about what happens when your input becomes arbitrarily large we're not interested in what happens when the input is small uh for this reason you'll see that we ignore things like constants and multiplicative factors so in our Big O notation you'll often see these coming up again and again again so to clarify one thing when I say n n is usually always going to be the input size coming into your algorithm there's always going to be some limitation of size n so constant time we refer to as a one wrapped around a big O if your algorithm takes a logarithmic amount of time to finish we say that's Big O of log of n if it's linear then we just say n if it takes like quadratic time or cubic time then we say that's n raised to that power if it's exponential uh usually this is going be something like 2 to the N 3 to the N any number be greater than one to the n and then we also have n factorial but we also have things in between these like square root of n log log of n n the 5th and so on um actually almost any mathematical expression containing n can be wrapped around a big O and is Big O notation valid now we we want to talk about some properties of Big O So to reiterate what we just saw in the last two slides Big O only really cares about what happens when input becomes really big so we're not interested uh when n is small only what happens when n goes to Infinity so this is how and why we get the first two properties uh the first that we can simply remove constant values added to our bigo notation because if you're adding a constant to Infinity well that's just infinity or if you're multiplying a constant by Infinity yeah that's still Infinity um so we can ignore constants but of course this is all theoretical in the real world if your constant is of size 2 billion yeah probably um that's going to have a substantial impact on the running time of your algorithm um however let us look at a function f which I've defined um over some input size n if F of n is 7 log of n Cub + 15 n^ 2 + 2 N Cub + 8 well Big O of f of n is just uh n cubed because n cubed is the biggest um most dominant term in this function all right now let's look at some concrete examples of how big O um is used so both of the following run in constant time with respect to the input size n because they don't depend on N at all so on the left when we're just adding or doing some mathematical formula yes that's constant time and on the right okay we're doing a loop but the loop itself doesn't depend on N so it runs also in a constant amount of time so as our input size gets arbitrarily large well that Loop is still going to run in the same amount of time regardless now let's look at a linear example so both the following actually run in linear time with respect to the input size n because we do a constant amount of work n times so on the left we're incrementing the counter I by One each time so F of n is n and clearly when we wrap this in a Big O we get a big O of n on the right uh a little bit more complicated we're not incrementing by one we're incrementing by three so we're going to finish that loop three times faster so f ofn is n over3 so our second example is two algorithms that run in quadratic time so the first one seems obvious we do n Work N times so n * n is Big of n^ 2 but observe the second one I changed uh the zero with an i so pause the video and try to figure out maybe why that's uh big of N squared okay let's go over the solution so first just focus on the second Loop uh the first Loop isn't as uh important so since I goes from Zer to n the amount of looping done is going to be directly related to what i is and remember I is changing from the outer loop so if we fix I to be zero we do n work if we fix I to be one we do n minus one work if we fix I to be two we do n minus 2 work and Etc so the question then becomes what is n + nus1 plus nus 2 plus nus 3 and so on well this is a well-known identity and it turns out to be n * n + 1 uh / two so if we wrap this in a Big O we split our equation we can see that this is Big O of N squared now let's look look at perhaps a more complicated example earlier you may have wondering how do we ever get these log rythmics or linear rythmic time complexities so here's a classic algorithm of doing a binary search which yields actually a logarithmic time complexity so what this algorithm does is it starts by making two point errors uh one at the very start and one at the very end of the array then it selects a midpoint between the two and checks if the value we're looking for was found at the midpoint and then it has either found it or not if it has found it it stops otherwise it discards one half of the array and adjusts either the high or the low pointer remark that even in the worst case we're still discarding half of the array each iteration so very very very quickly we're going to run out of a rate to check so if you do the math the worst case is you will do exactly log base 2 of n iterations meaning that the binary search will runs in logarithmic time very cool algorithm a very powerful algorithm here's a slightly different example worth going over so first notice that there is an outer loop with a counter I that does n work then notice that there are two inner Loops one that does 3 n work and another one that does two n work so the rule we use to determine the complexity of this algorithm is to multiply loops on different levels and add those that are on the same generally speaking uh so so using the rule above we can see that it takes n work to do the outer loop multiply by 3 n + 2 N for both inner Loops which gives us 5 n^ 2 which is Big O of n^2 all right so this next one looks very similar but it's actually quite different so on the outer loop with I we have I going from 0 to 3n so there's 3 n work done on the outside but we have to multiply that by what's going on on the inside so on the inside J goes from 10 to 50 so that does 40 Loops exactly every Loop so that's a constant 40 amount of work plus however the second Loop so J is less than n cubed but J is uh Jal J + 2 so it's accelerated a little so we're going to finish that Loop a little faster so we're going to get on the inside 40 + n cubed / 2 but we have to multiply that for by 3 n so if we wrap that in a Big O So Big O of f of n is going to give us Big O of n 4th because n 4th is the dominant term in our function f of n there some other classic examples of Big O so if we have to find all the subsets of a set that takes an exponential amount of time because there are to the N subsets finding all permutations of a string takes big O of n factorial uh another classic one is merge sort so if we have n * log n for your merge sort and if we have to iterate over all the cells of an array of size n by m we have Big O NM uh time