What is Big O
Before I go anywhere
Use this:
Big O Cheat Sheet
Intro Example
I am a big fan of analogies because they make it easy for smart people to explain complex things to….well, people like you! You are so smart, who’s a little smarty? It’s you! It’s you!
Alright, let’s say you have to solve a problem, like washing the dishes, and you have 3 workers. Each worker will be so efficient at a task, I won’t get too mired down with the details since it would be too confusing for your tiny…uh, never mind.
When you assign these workers, there is a best way, an average way, and a worst way. And you cannot always control how that turns out. Like worker one’s sippie cup might have spilled, and now he won’t agree to dry the dishes. You can try to force him, but he unionize with the other works, or worse….tell his mother. shudder So you have to deal with that and assign him to a different task. This situation is exactly like Big O, Theta, and Omega. It is a way to tell people, in the best conditions this is how efficiently I am solving this problem, in the average case, this is how efficient, and in the worst case this is the case. So which is which?
Which is which?
Big O- The workers revolt
Big O is the worst case scenario, all of your most efficient workers have decided that they will not do the job that is best suited to them. Instead, they want to do the job they are the worst at. It’s like a clown trying to be funny, or my wife trying to love me, just not a good fit.
How does this apply to the real world? And by real world I mean digital world of computer programming. Let’s say you have to sort a list of items. In the worst case, the items would be sorted, but in reverse order. The exact WORST possible situation. So, that is where Big O lives. Big O says, everything has gone wrong. Everything is terrible. No one wants this, but we still have to solve this problem. How efficient are you now?/ The lower your Big O, the more impressive it is.
Notation: O(1), O(N), O(N!)...etc
Big Omega- The workers are happy
Big Omega is the case where all workers are happy, and they do the perfect job for them. Instead of everything going wrong, everything is going perfectly, and nothing bad can touch you here. It’s a lot like kids in college, idealistic and perfect. This is if you have to sort a list, and it is already sorted. HOORAY! On the flip side, the worse your Big Omega is, the more unimpressive it is.
Notation: Ω(N) OR Omega(N)
Time to pause to experience the irony. Big O is all about the worst possible case, everything is terrible, and yet it is the best place to impress someone. While Big Omega is all about the best case, everything is great, and it is the easiest way to show someone you are a big moron. Just something interesting to ponder, if you don’t see the irony, don’t worry. It’s because your big brain is too big to comprehend it. Who’s a good reader? It’s still you! It’s still you!
Big Theta- The Workers Have Unionized
Let’s say that you have your three workers, and they decide that they always want to accomplish the task in the relative amount of time. They always want to finish the job in an hour. So, even if Brian spills his sippy cup, or Joan falls down the stairs.... again. They will guarantee that the job will always be finished in an hour. This could look different and happen in many ways, but it’s not important. The concept is the important part.
If you can solve a problem and your Big O and Big Omega are the same, then you have a Big Theta. Not all problems have a Big Theta, since sometimes in the best case you will be able to solve a problem quickly, while the worst case will take much longer. These concepts are basic, but they are important for you to move forward. In life no one cares about the best case, because we aren’t college kids. We live in the real world. And if you can solve problems under the worst conditions, then we know how much you are worth.
Notation: Ө(N) OR Theta(N)