In a recent post, I mentioned Big O notation:
Simply put, Big O notation is used to describe the running time or space requirements of executing an algorithm as the size of the input to the algorithm increases. The differences between two functions that do the same thing, but in different ways (like iteration vs. recursion), becomes very clear when you consider very large datasets passed into the algorithm.
Big O focuses on the worst-case requirements of running an algorithm, which can be referred to as the upper-bound of the growth rate.
I thought I should expand on this and share some good resources for learning more about Big O. It can be a bit confusing to understand at first. I’ve found that different sites explain it differently, using different examples. So some examples might make more sense to some people, which can help immensely when learning something like Big O.
For the record, here’s the definition of Big O from Wikipedia:
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.
Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.
The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.
The main point here is, what are the worst-case requirements (in terms of space or time) that will be needed to run an algorithm as the input gets huge. If you remember to think in terms of huge amounts of data being fed to your algorithm to process, you’ll understand why things like smaller exponents, multipliers and additions are simply ignored (because they become irrelevant as the data gets larger, compared to the lead exponent).
Take a look at some of these references to find one that connects for you:
- Big O Notation in JavaScript (Cesar’s Tech Insights on Medium.com)
- Using not-boring math to measure code’s efficiency (Interview Cake)
- Big-O notation (Khan Academy)
- Big O notation (freeCodeCamp)
- A beginner’s guide to Big O notation (Rob Bell)
If you feel like you’re struggling, this article may help improve your outlook (despite the ominous title):
- 10 Signs You Will Suck at Programming (Noteworthy - The Journal Blog on Medium)
Good luck!