So over the past week, I realized how important it was to start learning Data Structures and Algorithms. One of the topics that I covered at the beginning of my Bootcamp is something called Big O Notation, which I’m going to be writing about it in today’s post. There are numerous ways to calculate and solve many different problems in soft engineering and programming, big O notation is one of the ways that we can find the most efficient way to solve a problem. Big O can show and teach the differences between solving a problem one way versus another. We’re trying to figure out how big algorithms can grow with respect to the size of their input. The output is how much time is required to
“ Big O notation, an equation that describes how the run time scales with respect to some input variables” — HackerRank, 2016.
Let’s simplify this.
While watching YouTube videos to fully understand this concept, I came across a comment from Christine Hill that really gave me a better understanding, hopefully, it helps you too. I’m going to write it out as I interpreted it, however, so that I can make sure I’m learning as I write down this blog post.
Let’s say you’re making dinner for your family. ‘O’ Would be the process of following a recipe for a specific dish, such as spaghetti. The number of times that you follow that recipe is dubbed ‘n.’ Now when I cook, I cook family-style — meaning that only one big dish of spaghetti would be needed to be made. The recipe for feeding five people with one dish needs to be followed one time. Or an O of 1, where n is equal to 1. Now let’s say instead of being at home, I’m head chef at a restaurant (clearly, because I actually do really enjoy cooking), and I’m cooking for 10 different people, I would make 10 separate dishes, following the recipe 10 different times. This results in O(n), where you follow the recipe from top to bottom for the different number of people you are serving.
Essentially big O is a great way to determine the complexity of code, with its relationship to time, in algebraic terminology (Undefined Behavior 2017). Big O(n) is a linear equation so that basically means that it is running at the same constant time and speed for eternity. All sloped lines will fall under the same big O. Big O(n^k) Is known as polynomial time, over long periods of time linear equations of big O can sometimes appear to be faster, but in the long run, polynomial-time will always be faster than linear time.
Big O is best used to find the worst-case when determining and analyzing a problem, for most problems it is ideal to determine the best case, average case, and worse case. This way we can be prepared for what may or may not happen. The run time of an algorithm can often depend on a specific input, some algorithms can allow the code to run better or worse.
Big O can help us determine how much space an algorithm is using. This helps us with larger data sets or devices with lesser memory capabilities. Big O erases constant variables, but in some cases those are important. When we need performance, such as a video game, we might need to spare each bit of computation — even if it doesn’t alter the big O run time. Exponential growth isn’t continuously terrible in the event that the input is always small. We may some of the time with a more awful big O on the off chance that other components are more critical. I hope you enjoyed my brief entry to Big O, there is most definitely more as I have barely scratched the surface and hopefully gained your interest!
As stated best by Justin Chen, Brandon Chen, Elaine Chang, Zachary Greenberg in Undefined Behavior,
Some times slow and steady doesn’t win the race. — 2017
