38: Big-O Notation. How Fast Can You Go?

There are some common Big-O notations that you should become familiar with as well as what kind of code leads to them. This episode continues the discussion of Big-O notation so make sure to listen to episode 37 first. Knowing the signs of these will help you write more efficient code and for some of them could actually mean the difference between your program working vs. never completing at all. Here are the Big-O notations in order of execution speed from fastest to slowest: Big-O (1) runs in constant time no matter how big your problem becomes. Big-O (lg N) runs in time proportional to the log of N. Big-O (N) runs in time proportional to N. Big-O (N lg N) runs in time proportional to N times the log of N. this will be a little slower than just N. Big-O (N2) runs in time proportional to N times N. You might also find varieties of this such as Big-O (N3) Big-O (N!) forget about this completing at all for items in the mid to upper teens. This really starts becoming impractical with N as small as just 10. Note that there are more Big-O notations than just these. But learning these will help you understand almost all the situations you’re likely to encounter. And hopefully, you don’t come across N factorial at all. Listen to the full episode or you can read the full transcript below. Transcript You’ve already learned about a linear algorithm. That’s one where the code must perform some amount of work on each item. Your first question might be what’s an item? As long as you can divide the work into specific and separate tasks performed on specific pieces of information, then you have items. How many items you have is the key to understanding Big-O notation. You see, Big-O notation doesn’t talk about one hundred items or one thousand items or any specific number. We take it to the limit and just refer to the number of items as N. That’s a capital letter N by the way. A linear algorithm is referred to as Big-O of N. Whenever you see this, you know right away what the code will be doing, it will be moving from one item to the next until it decides to return. It’s important to realize that the code doesn’t have to actually visit each item. It might decide after 5 hundred items that it has enough. It could even decide on the very first item that the algorithm is done and the answer is ready. It doesn’t matter. This is still a Big-O of N or a linear algorithm. The reason for this is because while the algorithm might sometimes decide to return early, it’s also just as likely to need to keep on working. If you have somewhere in your code a for loop or a foreach loop that moves from one item to the next sequentially, then you have a linear algorithm. You also learned about another way of moving about your items by going straight to the middle item and then up or down the items by another half. This type of algorithm doesn’t go through a hundred items one by one. It’s able to eliminate half of the remaining items each step of the way. Let’s say you have one hundred numbers that have been sorted so the smallest number is first and the biggest number is last and you’re looking to see if the number 75 is anywhere in this list. Well, since you know that you have one hundred numbers and they are already sorted, you go straight to the number at position 50. If the number at that spot is less than 75, then you know that 75 can only be in the second half if at all. You just eliminated the first 50 numbers without looking at them at all. The you divide the second set of 50 numbers in half by looking at the number in location 75. Note that this is the location 75 and not the value 75 you’re looking for. You keep doing the same steps but each time, you’re able to cut your work in half. When you get down to just a single item and it’s still not the value you’re looking for, then you can answer that the number 75 is not in the list of numb