Big O Notation

Key Takeaways

Hi, I'm Gail Lock Mcdow, author of Cracking Coding Interview. Today, we're going to cover one of my favorite topics, which is bigo or algorithmic efficiency. I'm going to start off with a story. Back in 2009, there was this company in South Africa and they had really slow internet they were really, really frustrated by. And they actually had two offices about 50 miles away. So, they set up this little test to see if it would be faster to transfer a big chunk of data over the internet with their really slow internet service provider or via carrier pigeon. Literally, they took a bunch of USB sticks or probably actually one giant one, strapped it to a pigeon and flew it from one office to the next. And they got a ton of press over this test and uh media kind of loves this stuff, right? And of course, the pigeon won, right? it wouldn't be a funny story otherwise. And so they got a whole bunch of press over it and people were like, "Oh my god, I can't believe that a pigeon beat the internet." But the problem was it was really actually kind of a ridiculous test. Cuz here's the thing, transferring data over the internet takes longer and longer and longer with how much data there is. With certain simplifications and assumptions, that's not really the case with pigeons. Pigeons might be really slow or fast, but it always basically takes the same amount of time for a pigeon to transfer one transfer some chunk of data from one office to the next. It just has to fly 50 miles. It's not going to take longer because that USB stick contains more data. So, of course, for a sufficiently large file, the pigeon's going to win. So in big O, the way we talk about this is we describe the pigeon transfer speed as O of one. It's constant time with respect to the size of the input. It doesn't take longer with more input. Again, with certain simplifications and assumptions about the pigeon's ability to carry a USB stick, but the internet time is internet transfer time is O of N. It scales linearly with respect to the amount of input. twice amount of data is going to take roughly twice as much time. So that's what bigo is. Bigo O is essentially an equation that describes how the runtime scales with respect to some input variables. So I'm going to talk about four specific rules, but first let me show you what this might look like in code. So let's consider this simple function that just walks through an array and checks if it contains a particular value. So you would describe this as of n where n is the size of the array. What about this method that walks through an array and prints all pairs of values in the array. Note that this will print if it has the elements five and two in the array, it'll print both 2a 5 and 5a 2. So you would describe this probably as o of n squared where n is the size of the array. You can see that because it has n elements in the array. So it has n squared pairs. So the amount of time it's going to take you to run that function is going to increase with respect to n^2. Okay. So that's kind of the basics of big O. Let's take another real world example. How would you describe the runtime to mow a square plot of land? So a square plot of grass. So you have this plot of grass and you need to mo mow all of it. What's the runtime of this? Well, it's kind of an interesting question, but you could describe it one of two ways. One of which, well, one way you could describe it is O of A, where A is the amount of area in that plot of land. Remember that this is just an equation that expresses how the time increases. So, you don't have to use N in your equation. You can use other variables and often it makes sense to do that. So you can just describe this as O of A where A is the the amount of area there. You could also describe this as O of S^ squ where S is the amount of is this length of one side because it is a square plot of land. So the amount of area is S^ squ. So it's important that you realize that this O of A and this O of S squ are obviously saying essentially the same thing. Just like when you describe the area of a square. Well, you could describe it as 25 or you could describe it as five squared. Just because it has a square and it doesn't make it bigger. So, both are valid ways of describing the runtime. It just depends on what might be clear for that problem. So, with that said, let me go on to four important rules to know with big O. The first one is if you have two different steps in your algorithm, you add up those steps. So if you have a first step that takes, you know, O of A time and a second step that takes O of B, you would add up those run times and you get O of A plus B. So for example, you have this runtime that you you have this algorithm that first um walks through one array and then it walks through this other way. It's going to be the amount of time it takes to walk through each of them. So So you'll add up their run times. The second way, the second rule is that you drop constants. So let's look at these two different ways that you can print out the min and max element in an array. One finds the min element and then finds the max element. The other one finds the min simultaneously. Now these are fundamentally doing the same thing. They're doing essentially the exact same operations just doing them in slightly different orders. Both of these get described as O of N where N is the size of the array. Now, it's really tempting for people to sometimes see two different loops and describe this as O of 2N. And so, it's important that you remember that you drop constants in big O. You do not describe things O of 2N or O of 3 N because you're just looking for how things scale roughly. Is it a linear relationship? Is it a quadratic relationship? So, you always drop constants. The third rule is that if you have different inputs, you're usually going to use different variables to represent them. So let's take this example where we have two arrays and we're walking through them to figure out the number of elements in common between the two arrays. Some people will mistakenly call this as O call this O of N squ, but that's not correct. When you just talk about runtime, if you describe things as O of N or O of N squ or O of N log N, N must have a meaning. It's not like things are inherently that one or the other. So when you describe this O squ, it really doesn't make sense because it doesn't you what what does N mean? N is not the size of the array if there's two different arrays. What you want to describe instead is O of A * B. Again, fundamentally big O is an equation that expresses how the runtime changes, how it scales. So you describe this O of A time B. The fourth rule is that you drop non-dominant terms. So let's suppose you have this code here that walks through an array and prints out the biggest element and then for some reason it goes and prints all pairs of values in the array. So that first step takes O of n time. The second step takes o of n squ time. So um you could first get as a you know less simplified form you could describe this as O of n + n^2 but note that you know compare this to of n and the runtime or compare this to the runtime of n^2 and the runtime of n^2 + n^2 both of those two run times reduce down to n^2 and what's interesting here is that of n plus n^2 should logically be between them. So n this n squ thing kind of dominates this O of N thing. And so you drop that non-dominant term. It's the n square that's really going to drive how the runtime changes. And if you want, you can look up a more academic explanation for when exactly you drop things and when exactly you can't. But this is kind of the layman's explanation for it. We've now covered the very basic pieces of bigo. This is a incredibly important concept to master for your interviews. So, don't be lazy here. Make sure you really, really understand this and try a whole bunch of exercises to solidify your understanding. Good luck.