Demystifying The Big O(bsession) Part II
In Part I, we introduced Big O, talked about why we should care, and analyzed the Big O of an algorithm. Today, we’ll get a little more technical, cover some common time complexities, and touch a bit on space complexity. Let’s go!
So we’ve discussed that Big O is a way of measuring the performance of an algorithm. The good news is that there are some basic rules you can follow to get the Big O of an algorithm and there are only a limited number of common time complexity patterns. All of these patterns are based on the shape of the growth curve that results when plotting a graph of input size versus runtime, i.e. an algorithm that runs in linear time (such as the one we discussed in Part I) can be represented by a linear growth curve. The rules are as follows:
Rule 1: Check the number of operations the algorithm will perform relative to its input size (n) given its worst case scenario. We’ve spent some time discussing what this means and following through with an example in Part I, so I won’t go into the nitty gritty details, however this is an important rule to mention as it’s the pure essence of Big O. For example, if we have an algorithm that will loop through an array that changes size based on its input, that’s O(n).
Rule 2: Drop the constants. When determining Big O, you may discover that you need to loop through the same array twice or do some operation a constant number of times. Instead of specifying these constants as O(2n) or O(5n²), we simply drop these constants to get O(n) or O(n²). In the grand scheme of things, these constants don’t influence our Big O, because Big O only cares about the long-term growth curve. While throwing in a constant will change the runtime by a constant amount, the shape of its growth curve will remain the same, rendering the constant insignificant. For instance, a linear function will still have a linear growth curve and an exponential function will still have an exponential growth curve despite any constants.
Rule 3: Only include the bottleneck (the highest order term). Say we have a function such as below that does many different operations. It includes some loops, some of which are nested and some of which aren’t, and maybe does some operations outside of the loops.
function example(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
console.log(array[i] + array[j])
}
}
for (let i = 0; i < array.length; i++){
console.log(array[i])
}
console.log(array[0])
}This type of multi-operational function is much more representative of the kind of algorithm a developer may write when solving a problem — after all, most problems require multiple steps to solve them. It’s important to note that every operation in the function may have a different time complexity. In our case, the nested for loop is O(n²), the non-nested for loop is O(n), and the last console.log is O(1). So how do we specify the time complexity of such an algorithm? All we need to do is state the highest order term — O(n²) — that’s what will shape our growth curve and slow down our program the most. That’s our bottleneck!
Common Time Complexities (best to worst)
So I’ve been throwing around a few Big O notations such as O(n²), O(n), and O(1). Let’s actually discuss these and some other common time complexities we may run into out in the wild. Check out the graph below for a sneak peek.
O(1)
Known as constant time, this is the absolute best time complexity we can achieve. It essentially means that the input does not affect the number of operations this algorithm performs. For example, if we were to write an algorithm that returns the first element of an array, the size of the array doesn’t matter. Some other examples include: accessing the nth element in an array; accessing a key in a given object (also know as hash or dictionary); or doing a math operation (such as summing two numbers).
One thing to note is that O(1) doesn’t mean the algorithm only performs one operation — it could perform 1000 operations for all we know (which we simplify to O(1) by dropping constants). All it means is that the number of operations (whether it’s 1 or 1000) will be the same no matter the input. See the example below:
function countToFive(){
for (let i = 1; i <= 5; i++){
console.log(i)
}
}Despite the loop, this function runs in constant time because the loop will always perform 5 iterations- no less and no more.
O(log n)
Also known as logarithmic, O(log n) is the next best time complexity we can achieve, although it’s a bit trickier to understand. Thinking back to high school math, a logarithm is the inverse of an exponent. So if 2³= 8, then log2(8) = 3. To obtain 3, we need to ask ourselves “2 to what exponent produces 8?” Here’s why O (log n) is so great: whereas an exponential time complexity(like O(n²)) will double our runtime when increasing the input size by just one, O(log n) will need to double the input size to add just one operation to this time complexity! To put that into perspective, given an input size of 1 million, we will only need to perform 20 operations in the worst case scenario using O(log n).
Of course, not every algorithm can be written in O(log n) time. Usually, the kind of algorithms that can be written in O(log n) are those with sorted arrays as inputs. A very common example is writing a binary search for an array of sorted numbers. In a binary search, we would check the middle of the array for our target number — if our number is smaller than the middle number, we can remove the entire second half of the array knowing that it cannot appear there; if our number is larger, we can remove the entire first half of the array. We will then use the half of the array that we kept as our new input. In this way, we remove half of the input size with every check that we do, and this is a much more efficient solution than checking every single element in the array (which would otherwise be O(n) time).
O(n)
O(n) time (also known as linear time) means that given n input, the algorithm will need to perform n operations. The runtime of this algorithm is directly proportional to the input size, and the shape of the growth curve will be linear as below:
A good indicator of linear time is an algorithm that loops through every element in a given collection. In Part I, we used the example of looping through an array to find the first element above a target number.
O(n log n)
O(n log n), also referred to as linearithmic, loglinear, and sometimes quasilinear time, is a time complexity usually associated with sorting algorithms and it’s the best time complexity a sorting algorithm can achieve. Some examples of sorting algorithms that run in O(n log n) include Merge Sort and Heap Sort. Both of these algorithms adopt a common paradigm based on recursion known as divide-and-conquer. For example, the Merge Sort algorithm will recursively break the array to be sorted in half until it reaches inputs of 1 element. Then it will sort and merge together the newly sorted arrays.
O(n²)
Now we are getting into the territory of time complexities that are best avoided. O(n²) is a rather inefficient time complexity, sometimes known as quadratic or polynomial based on the shape of its growth curve (see below).
O(n²) algorithms are known for their runtime being proportional to the square of their input size. Usually an indicator of O(n²) runtime is an algorithm that uses a nested loop over one set of data. A typical example is an array that loops over itself and for every iteration, it loops over itself again. It is important to note that the nested loop should be over the same collection. If we were to loop through one array and then loop through a different array at every iteration, that would be a different Big O because we can’t assume that the arrays are the same size. Another thing to note is that more deeply nested iterations (more than two levels) will result in time complexities of O(n³), O(n⁴), and so forth.
See below for an example of O(n²) — an algorithm that loops through an array and returns all pairs that equal a target sum. This algorithm uses a brute force approach that loops through the given array n² times in a nested for loop. *Please be aware that a better Big O can be achieved for this problem.
function twoSum(arr, target){
const sums = [];
for (let i = 0; i < arr.length; i++){
for (let j = i + 1; j < arr.length; j++){
if (arr[i] + arr[j] === target){
sums.push([arr[i], arr[j]])
}
}
}
return sums;
}
twoSum([3, 5, 2, -4, 8, 11], 7) => [[5,2],[-4,11]]O(2^n)
Also known as exponential time, O(2^n) is one of the worst time complexities and should be avoided as much as possible. The most common algorithms that run in O(2^n) time usually take an input of size n and use recursion to solve two smaller problems of inputs n-1. A classic example is Fibonacci using the recursive solution:
function fibonacci(n){
if (n <= 1) return n;
else {
return fibonacci(n-2) + fibonacci(n-1);
}
}The reason that this solution is so inefficient is because every recursive call of this function produces two more recursive calls, which produce two more recursive calls, which produce two….you get the point.
O(n!)
O(n!), also known as n factorial, also known as Oh no! — just kidding about that last one — is the absolute worst time complexity that can be achieved. In math, the factorial of a number (n) is all positive integers multiplied by each other starting from n and decreasing by one. For example, 5! would be 120, which results from multiplying 5 x 4 x 3 x 2 x 1. Examples of algorithms that run in O(n!) are generating all permutations of a string and the famous traveling salesman problem. This famous problem provides a list of cities and distances between the cities, and it requires the traveling salesman to come up with the shortest route to visit all of the cities.
Putting it into Perspective
Now that we have analyzed the common time complexities, let’s put it into perspective to see how their runtimes compare. The below chart, taken from The Algorithm Design Manual by Steven S. Skiena, compares the time complexities we have analyzed today, except for O(1) (constant time) since the input will not have an impact on runtime. On the leftmost side, we can see varying input sizes starting from 10 to 1 billion. In the remaining columns, we can see how long each algorithm will take to run for each time complexity. This is a good reminder to always optimize code when solving problems as no one has 31 years to wait for an O(n²) algorithm to run.
Tips and Tricks
First, I’d like to mention that although we’ve analyzed the most common Big O Notations, it won’t do to just memorize each of them. It is important to know how to analyze Big O, as there are a couple of other notations you may find when paying attention. It is especially important to pay attention to inputs, especially when there are multiple collections involved. Let’s examine the below example:
function exampleOne(array1, array2){
for (let i = 0; i < array1.length; i++){
for (let j = 0; j < array2.length; j++){
console.log(array[i] + array[j])
}
}
}At first glance, we may be tempted to infer that the Big O of this algorithm is O(n²) because of the nested for loop. However, we cannot assume that the two input arrays are the same length, so they must be treated as separate entities. Therefore, in a nested loop where the collections are not guaranteed to be the same size, the correct time complexity is actually O(n*m).
What about the example below?
function exampleTwo(array1, array2){
for (let i = 0; i < array1.length; i++){
console.log(array1[i])
}
for (let i = 0; i < array2.length; i++){
console.log(array2[i])
}
}Here, we may be tempted to assume that the time complexity is O(2n), simplified to O(n) because of the two non-nested loops. In this case, we are actually looping through two different collections, and once again we cannot assume that they will be the same size. Therefore, instead of O(2n) simplified to O(n), the correct time complexity of this algorithm is O(n+m). We use the plus sign this time because the operations happen one after another which adds to the time. We had to multiply in the previous example because the loops were nested, which multiplies the time complexity.
Another important note to mention when analyzing time complexity: beware of native methods! The native methods of most programming languages, especially array methods will likely add time complexity and they absolutely need to be accounted for. A good rule of thumb is to think about how one would implement a native method from scratch such as the JavaScript .find method. If in implementing the method from scratch, you would need to loop through every element in the array, then that native method will add O(n) time complexity. Let’s examine the example below.
function findMatchingElement(arr1, arr2){
for (let i = 0; i < arr1.length; i++){
if (arr2.includes(arr1[i]){
return arr[i];
}
}
}In the above example, we’ve written a function that looks innocent enough. We are cross-checking two arrays to determine if we can find an element appearing in both arrays. We do this by looping through one array and checking if the second array includes the element. The one for loop deceives many into believing this method runs in O(n). However, it is important to note that the native .includes method in JavaScript runs in O(n) under the hood. Therefore, the true time complexity of this algorithm is actually O(n*m).
A Note About Space Complexity
If you’ve made it this far and have understood how time complexity works, then you should have no trouble with space complexity. The Big O notations for space are written the same way as for time. The only difference is that instead of measuring how many operations an algorithm performs, we check how much extra space an algorithm allocates when it runs. To determine space complexity, we will usually check for any new variables that are declared when the algorithm runs. This will help us determine what we are storing in RAM as the algorithm runs and how much space those variables take up.
Let’s take a simple example:
function countUpToNum(num){
let i = 1
while (num <= num){
console.log(i)
i++
}
}In the above function, we introduce a new variable on the second line which stores an integer. Now, integers and strings are primitive datatypes in JavaScript which cannot be mutated — therefore this variable (despite changing every time in the while loop) takes up constant or O(1) space.
What about other kinds of space complexity? Well, if we were to store a variable of an empty array or object that continues to fill up proportionally to our input size, our space complexity would be linear O(n). If we were to store a two-dimensional array or nested object, such as when filling up a matrix, then our space complexity may be O(n²) or O(n*m) depending on whether the inner and outer collections are the same size. Usually however, it may make more sense to rotate or sort an array or matrix in place to avoid adding space complexity. In a pattern similar to time complexity, the more deeply we nest, the worse our space complexity becomes.
Today, we discussed how to analyze the Big O of an algorithm in more detail. We touched on some rules to follow when analyzing Big O, we walked through the most common time complexities, and touched on space complexity. Until next time!
Any intelligent fool can make things bigger and more complex… It takes a touch of genius and a lot of courage to move in the opposite direction.
— Albert Einstein