Complexities of Big O Notation
A simple introduction
Thanks for the visit! Feel free to see more of my work and connect with me on LinkedIn.
What’s with Big O notation? This is an important concept to consider when solving algorithms and writing code. Simply put, Big O notation is a recognized standard of figuring out the efficiency and scalability of code. When figuring the complexity of an algorithm, it is generally expressed as a function of n. Where n is the size of the input.
There are a few different things to consider when analyzing Big O notation. Those being time complexity and space complexity. Basically, we are focusing on how efficient code is based on either the time it takes to reach the desired solution; or the amount of space required in memory to solve- in relation to the input size (n).
Time complexity (this is prioritized over space complexity)
As stated above, this is the amount of time the algorithm takes to complete its process based on a function of its input (n). Or we could think, “how does the runtime of this function grow.” Common terms for time complexity include:
O(1) → Constant Time meaning it always has the same run-time, no matter how big the input is. For example, 1 + 1 will take the same amount of time to perform as 1,000,000 + 1 or when setting a var x = 2 is the same as setting var x = 2,000
O(n) → Linear Time this means that the processing time increases linearly (at the same rate) with the size of the input
O(n²) → Quadratic Time the processing time increases exponentially as the input increases. Using nested loops is one example that causes your code to have O(n²) time complexity
Space Complexity
This is based on the amount of memory (RAM) an algorithm needs as the input (n) begins to get larger
O(1) → Constant Space Just as the time complexity above, this takes up the same amount of space no matter the input. For example, setting var x = 200 takes up roughly the same amount of space as var x = 500
O(n) → Linear Space the space needed is directly correlated to the size of the input. For example, when storing a string, object or array the space needed for 2 of those things is half as much as storing 4 of those things
Now that we have seen some examples of time and space complexities, we have a better grasp on what to strive for when writing code. Below is a cheatsheet to better visualize each scenario. You can see that the ideal place for your code to be is nearest the x-axis. Meaning that the code takes up the least amount of time and space to reach its desired solution regardless of the input size.
With all of this new information, I encourage you to dig a bit deeper. Try to analyze your code; be it algorithms, a personal project or in an interview setting. This will come in handy.
As always, leave any comments, suggestions and claps below if you feel inclined to do so. Happy coding!
