Different run times
Factorial - Death is your only saving grace
The notation: O(n!)
What it means: Literally the worst time you can get
Where Will You See It:
If you were a panhandler and needed to get money from as many people as possible, but you did not want to waste your time. Let’s say you are low on food, and you need to use every calorie as efficiently as possible. So, you are going to 3 houses, how do you find the most efficient route. You calculate the distance from house 1 to 2, then 2 to 3. THEN you calculate the distance from house 2 to 1, then 1 to 3. Then you calculate the distance from 2 to 3, then 3 to 1. And so on. This is a version of the Traveling Salesman problem. It is part of a special series of problems, which we will touch on later.
If you need to calculate “all possible” or “everything”…pretty much if someone is like “Hey, there’s a ton of stuff in this thing we got, and we need to know what the best way to get through all of it, including between them.” It is probably in this class of problems. Specifically, if someone asks for all permutations, it’s Factorial.
Exponential - Sell the house, invest in seeds
The notation: O(2 N)
What it means: This problem sucks, but at least it’s not factorial.
Where Will You See It:
The above example is still a good way to demonstrate this class. Let’s say that you figure out there are certain routes which are efficient, and there is no way to beat them. Like if the house 1 and house 2 were right next to each other, so regardless of all other situations, you should travel to those houses one after another (be it 1 then 2, or 2 then 1). In this instance, you don’t need to compute every iteration. You will often see these types of solutions used in dynamic programming to solve factorial problems.
Show me the formula to determine a team of 11 people, out of 14 choices? If you have a team of 14 people, with only 11 open spots, how many possibilities are there? n!/ k!(n -k)! Why? What does that mean? Go through it one by one. In the first choice you have n options, then n -1, and so on. After we have selected a number of players, we have n - i choices left. What is that n-k! doing on the bottom? Order does not matter, unlike in other problems. Because a team with Johnson and Briggs, is the same as a team with Briggs and Johnson.Polynomial - Buy a bunker, and start filling it with canned peaches
The notation: O(N 2)
What it means: This problem sucks, it is going to be expensive to solve
Where Will You See It:
What if you wanted to be a matchmaker, but you were really bad at it...like you are at.....well, just remember what your mom always told you as a kid. If you had 4 people, and you wanted to make everyone happy, they would all go on a date. Person A with B, A with C, and A with D. Then B with C, B with D, C with D. And you are done! This is different from Factorial, because person A matches with B, which means B does not have to match with A, they have already gone on a date!
Linearithmic - Leave grandma and get in the van
The notation: O(N lg N)
What it means: So.... you are sorting something?
Where Will You See It:
Sorting. Just memorize that, if you can. If you can't, quit programming. Not all sorting algorithms sort that quickly, but the absolute best ones sort that quickly. Quick Sort, Merge Sort, etc. It is slightly worse than O(N), but if you need to go through a bunch of things and you cannot get better time than O(N^2), then sort it. I will touch on this subject later, when we talk about...sorting. Kind of obvious, but you never know.
Linear - I guess we can keep the kids, for now.
The notation: O(N)
What it means: You only need to look at everything once
Where Will You See It:
So, God help us, I am going to have explain an abstact concept to you. You can get O(N) in time complexity if you have to go throught the elements only once. However, it can also happen if you have to go through the same elements over and over again. I.e. If you have an array [1,2,3,4, 1]. You go through, and delete duplicates one at a time. First you would delete the 1 at the end, but then you have to go through and check it one more time. In this case, you are doing two passes of the array, but that is 2N, and in Big O we do not care about integer values. So, your time is reduced down to O(N)
Logarithmic - Let's take that vacation after all
The notation: O(lg n)
What it means: Someone else did some work, and now you profit from it.
Where Will You See It:
Congrats, you are doing Binary Search. I am so proud of you. Or you are working with a certain graphs. This means that you only need to look at half of the data you are given. Probably because you are looking for a number or name in a sorted list of numbers/names. If someone says the word sorted, think "can I use binary search?" It won't always work, but sometimes it will. Also, this will come up in reference to Binary Search Trees, AVL trees, and Red and Black trees. You will learn more about these subjects later.
Constant - Buy lottery tickets, quit your job, and relax
The notation: O(N)
What it means: Solving this problem is unimportant
Where Will You See It:
Does the answer exist somewhere in a dictionary/hash? In terms of solving a problem, it is not going to be frequent that you will be expected to solve something with constant time. It might be possible to use constant space, which is an important part of Big O, so don't forget to analyze your space complexity.