A Little Guide to Big O
Big O is a topic I’ve mentioned frequently on this blog, for good reason. In an interview setting where you are writing an algorithm, it’s very likely that you might be asked to explain the Big O notation of said algorithm. So today, let’s take a look at what exactly Big O notation is and understand how to determine the Big O notation of our algorithms.
What Even Is Big O?
Big O is kind of a broad concept in that it has an academic meaning and a more common, “industry” meaning.
In academic terms, big O refers to the upper bound on the runtime of an algorithm. For example, a simple algorithm to print the values of an array could a big O runtime of O(N). Or O(N³). Or any runtime bigger than O(N). If you’re a little confused on how exactly that makes sense, think of it like mph in a car. Assuming that no car can drive faster 300mph, you could say that my subaru legacy is driving at x (where x = speed in mph) ≤ 300mph. You could also, however, say that my car is driving at x ≤ 500mph. Or x ≤ 1000mph.
To understand the industry use of Big O, however, we might want to also understand a couple other related terms.
Big Omega is a term quite similar to Big O. Instead, however, of denoting the upper bounds of an algorithm’s runtime, it describes the lower bounds of a runtime.
Big Theta, then refers to both the Big O and Big Omega runtimes of an algorithm. Basically, it gives us a tight bound on the runtime. And, in industry terms Big O is essentially referring to the Big Theta runtime. For example, even though academically you could describe our simple printing algorithm as having a Big O of N³, in industry speak it would be correct to use the Big Theta term and just say that our runtime is O(N).
Determining Big O: Drop Everything
Big O basically allows us to discuss and understand how runtime scales. For this reason, an algorithm that you might want to describe as having a O(2N) runtime, would actually just have an O(N). That 2 won’t drastically change or alter the rate of increase of our algorithm and thus we can drop the constant.
For similar reasons, we can also drop the non-dominant terms. For example, if we have an algorithm with O(N² + N), we can simply drop our non-dominant N and just say that our algorithm has a runtime of O(N²). Although the N is not a constant like our above 2, if we don’t care about the 2 in O(2N²) (aka O(N² + N²), then why would we care about an extra plain N?
We wouldn’t.
Determining Big O: Multiply vs. Add
Let’s say we have an algorithm with two steps. How do we determine the Big O notation? Well, probably not to your surprise, it depends on what exactly those steps are.
If our algorithm is for example printing out items in an array and then separately printing out the indices of those items in the array (or basically doing A chunk of work and then B chunk of work), we would add the runtimes as say our Big O is O(A + B).
On the other hand, if our algorithm doing B chunk of work for each element in A, then we would say that algorithm has a Big O of O(A * B).
To clarify, if you algorithm does one thing and then subsequently does another, the runtimes would be added. If you algorithm does one thing for each time you do another, however, the runtimes would be multiplied.
Determining Big O: Log N
An algorithm likely to have a Log N runtime is one in which the number of elements in the problem space gets halved each time. A great example of this is the binary search algorithm.
Determining Big O: Recursion
I won’t lie, I find determining the Big O notation of a recursive algorithm to be difficult. However, if you have a recursive function that makes multiple calls, then runtime of that algorithm can often be determined by O(branches^depth) wherein branches is the number of times each recursive call branches. For example, if every time your algorithm was called recursively, it branched twice then your runtime would be O(2^n).
Space Complexity
Before we go, I’d like to note that time is not the only factor that matters in an algorithm. We also often care about the amount of memory (aka space) an algorithm requires. Fortunately, this space complexity can be discussed in very similar ways to our time complexity. For example, if we need to create an array of size n, it would require O(n) space.
