Big O Notation
The language used for discussing how long an algorithm takes to run.
Big O Notation is the language that allows us to measure the idea of how scalable our code is and how long it takes to run.
What is good code?
Good code can be described with two points:
- Readability: how readable is our code?
- Scalability: How adaptable is our code to new requirement?
As an example, let’s assume we are going to be making a dessert item. Our ingredients include eggs, milk, and cheese. Once we arrive home, we need to take our ingredients and follow a list of instructions to create our dessert item. Once we are done we would then have our dessert item to enjoy, yum!
In terms of programming:
- our ingredients is our data or input
- our instructions is our functions, code and algorithms
- our dessert item is our end result or output
There are good ways and a bad ways to make our delicious item. Hopefully the way we make our item is efficient as possible and simultaneously tastes good as well. Just like there are many ways to make our dessert item with different ingredients and instructions, there are many ways to solve a problem through code.
Let’s use our example from above to find a particular item. In our grocery cart let’s assume we have our milk, eggs, and cheese.
We’re trying to find a particular item. Using code, let’s write a function that searches through our grocery cart, and tells us whether or not we found the item.
How can we measure the Big O Notation or efficiency of this code? What happens if our grocery cart had more items? Or how do we handle the case of two or three grocery carts?
Scalability
Allows us to measure the performance of our function as the number of inputs increase. Below is a snapshot of the Big O complexity chart.
When we talk about Big O and the scalability of our code, we are discussing how our algorithm or function slows down as the number of inputs increase.
If the number of grocery items in our cart increase, how long or how many operations will it take to find the item we are looking for? We cal this concept algorithmic efficiency.
Big O Notation allows us to explain this concept. Below is a cheat sheet for reference.
