Introduction to Big-O

All right, now that we we're 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 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 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, um, usually this is going to be something like 2 to the n, 3 the n, uh, any number b greater than 1 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 n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n to 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. So now 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 two billion, yeah, probably um that's going to have a sub 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 uh 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 of n is n over three. 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 0 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 minus2 work and etc. So the question then becomes what is n + n -1 + n - 2 + n - 3 and so on. Well this is a well-known identity and it turns out to be n * n +1 uh / 2. 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 at perhaps a more complicated example. Earlier you may have wondering how do we ever get these logarithmics or linear rhythmic 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 quickly, we're going to run out of array 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 well runs in logarithmic time. Very cool algorithm, 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 2n 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 multiplied 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 3 N. 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 J= 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 cub / 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's 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 two the n subsets finding all permutations of a string takes big 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 of n m uh Time.