The Difference Between Quadratic, Exponential and Factorial Time Complexity
From Bad to Worst
Introduction
Combinatorics is a field of mathematics that deals with different ways of arranging or choosing items from a set and is important for things like statistics and probability.
It’s also useful for understanding some of the worst time complexities out there because, as you can probably imagine, as you increase the number of things you mix and match, the number of unique arrangements that you can create grows very quickly.
The more clothes you have, the more outfits you can wear. The more ingredients in your fridge, the more meals you can eat. And the more options you have, the more comparisons you need to make. In a way, combinatorics is at the heart of the paradox of choice.
Essentially, the more choices you have, the more difficult it becomes to make decisions quickly.
I wrote an article not too long ago about how to solve the Power Set problem, which I’ll refer to a degree throughout this post, so if you haven’t checked that out yet here is the link:
It’s a problem that runs in exponential time complexity, or O(2^N).
And while most of us probably have a pretty good sense that exponential is a very bad complexity, and our code will start to run VERY slowly with even relatively small input sizes, I want you to come away from this post with having a much more solid understanding of just how bad it is.
Because I’ve often heard engineers that I’ve coached say that a problem ran in exponential time just because it felt like the amount of work a problem did for larger inputs grew at a greater than linear rate. When in fact, often times the complexity was only quadratic O(N²) or was even worse, factorial O(N!).
This shouldn’t be something you leave up to chance in an interview setting, and it’s best to be able to answer complexity analysis questions about your algorithm solutions quickly and confidently. Because you will run into situations where the best solution you can give runs in something potentially far worse than linear time complexity.
Permutations v Combinations
One thing worth clearing up before jumping into the three different complexities we’ll be covering is just some basic terminology.
I often hear people use the term permutation and combination interchangeably, but in combinatorics, they mean very different things.
Combinations are generally considered in the context of picking some number of elements out of a larger set. A key thing about combinations is that you need to specify how many elements per combination.
Framed as a question, you could ask “how many combinations of two elements can you make out of a set of four?”
The answer is 6:
An important thing to remember about combinations is that the order of the elements in each combination is irrelevant. You can arrange the elements however you want because they are considered to be a set, which is an unordered collection.
Contrast that to permutations, where it’s all about the ordering.
Permutations are all the possible arrangements of a given set of elements.
You might ask “how many unique permutations are there of three elements?”
The answer once again is 6:
Now this rabbit hole starts to get pretty deep fairly quickly, so we’ll only really look at sets of unique elements, but something to keep in the back of your mind is how adding repeats to these sets might affect the outcomes of the complexities. Because there is only one permutation or combination of a set of identical items. But it’s a little harder to see what happens when there’s a mix of duplicates and unique elements. And this kind of curveball can show up in interviews.
So just given these two examples, you’d be forgiven for thinking that combinations and permutations had similar complexities. You can kind of see how you can start generating a lot of permutations or combinations from a fairly limited initial set of objects, but when you really dive into things you’ll start to see just how different they really are.
O(N²)
Let’s start with the first problem of trying to final all unique pairings of objects taken from a larger set.
You can do this in only a few lines of code:
function createPairs(arr) { let result = []; for(let i = 0; i < arr.length - 1; i++) { for(let j = i + 1; j < arr.length; j++) { result.push([arr[i], arr[j]]); } } return result;}console.log(createPairs([1, 2, 3, 4]))// [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
The first thing you might notice about this solution are the two nested “for” loops and most of the time when you’re first learning about quadratic time complexity, or O(N²), you’re told that this is a good indicator to look out for. And while there are a few exceptions to be careful with (see my sliding window post), for the most part, it’s a good thing to look out for.
But I also want to give you more of a visual/geometric understanding of how much work these nested loops are performing:
Because the inner loop starts where the outer loop left off, each round it is iterating through one fewer number than the previous round. Which makes sense, because you’ve already used that number in every possible pairing.
What this means is that you end up with a sort of triangle that is N units tall, and N wide. If you remember the formula for triangles it’s the height times the base divided by 2. And in complexity analysis, we simply drop the leading coefficient, which in this case is 1/2.
Now let’s look at what happens when you add another number, and for simplicity’s sake we’ll add it to the front of the array:
Just having that additional 0 at the front, means another full iteration through the whole array. In essence, by increasing our input by 1, we increase the amount of work we need to do by N.
As a fun fact, there’s a term for these numbers and they’re called the Triangular numbers, and also shows up in places like graphs when you want to find out how many edges can connect a given number of nodes (more on that in a future post):
I like looking at nested loops this way because it draws the geometric connection to iterating through an n-by-n matrix of numbers, and more broadly, m-by-n matrices. To me, that just seems very intuitive, since essentially all you’re doing is multiplying the number of rows, by the number of columns. And if you’re faced with something like a jagged array, all you need to do is take the average array length.
Now the next logical question is what happens when you want to find all the combinations of 3 items from a set of 4?
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]So it seems like you actually end up with fewer results, but what if we looked at all the combinations of 3 elements drawn from a set of 5? And how does that compare to only drawing 2 elements from a set of 5?
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]vs[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]
Now it looks like the sets of 3 have caught up. So if you had to make a prediction for how many unique combinations of 3 elements you could make by drawing from a set of let’s say 6 or 7 elements, would you expect there to be more or fewer combinations than if you make combinations of 2 elements?
And what would the time complexity of that process be?
Looking at the code we can see that there is a third “for” loop which would imply a cubic time complexity O(N³):
function createTriples(arr) { let result = []; for(let i = 0; i < arr.length - 2; i++) { for(let j = i + 1; j < arr.length - 1; j++) { for(let k = j + 1; k < arr.length; k++) { result.push([arr[i], arr[j], arr[k]]); } } } return result;}
Technically you could visualize this as some kind of 3-dimensional data structure:
If we wanted to find all the unique combinations of 4 elements, we could do that with an additional for-loop, and so on. What we’re exploring are the range of polynomial-time complexities, which include O(N), O(N²), O(N³), O(N⁴)… And we’re using the binomial coefficients formula to actually find how many unique combinations there are:
One thing worth noticing about how many combinations there are for a given input size, and combination size, is that you get the most around the middle. I’ll leave it up to you to think about intuitively why that is.
While it is rare to find these higher degree complexities on interviews they can occasionally pop up.
And the more general code for solving for any given size of combination uses recursion:
function combinations2(n, k) {
let result= [];function recurse(start, combos) {
if(combos.length === k) {
return result.push(combos.slice());
}
if(combos.length + (n - start + 1) < k){
return;
}
recurse(start + 1, combos);
combos.push(start);
recurse(start + 1, combos);
combos.pop();
}recurse(1, []);
return result;
}
But the main takeaway I want you to have from this section is that O(N²) (and all polynomial time complexities for that matter) are additive.
For algorithms that run in O(N²), anytime you increment the input size by 1, in have to perform N additional operations. This means that the amount of additional work depends on what the size of N is currently.
Now let’s look at how exponential functions differ in a fundamental way
O(2^N)
What happens when you add up all the combinations of different sizes?
Well, then you end up with the Power Set, or “set of all subsets.” To see why this function grows at an exponential rate, you can simply add up all the rows in Pascal’s triangle:
What each number represents in a particular row is how many unique combinations of a given size there are for a certain input.
So if you wanted the number of unique combinations of two elements, drawn from a set of four, you could just look that value up in the triangle like so:
Now if you add up all the values in a given row, you’ll see that each row adds up to be double the number of elements in the previous row:
This doubling is one of the key properties of the power set and it’s the main reason why exponential runtimes become so big so fast: you’re multiplying some value over and over again by itself.
And that’s the key difference between exponential and quadratic functions or any polynomial runtime functions: exponentials are multiplicative, and polynomials are additive.
Because of this fact, even something that runs in O(N¹⁰⁰) eventually will lose out to O(2^N). Multiplication will always beat addition.
Now technically you can have any base, like O(3^N), or O(57^N), and larger bases will grow faster than smaller ones, but they all fall under the category of exponential runtimes and the most common one you’ll encounter on interviews is O(2^N).
Places where you’ll usually see them pop up are binary trees, since adding another full layer of nodes effectively doubles the total number of nodes in them.
You’ll also see them in multiple recursive functions, like an unoptimized nth-Fibonacci function:
Some other famous examples are the “Traveling Salesman Problem” and the “N-Queens problem.”
But even though exponential growth is massive, and human beings are not great at grappling with those kinds of magnitudes, there is one more time complexity that is even worse.
O(N!)
One way to think of factorial functions is that they are to exponential functions what quadratics functions are to linear functions.
In other words, they dwarf them in the speed at which they become massive. It’s in a category of its own because no matter how big of a base you choose for your exponential, eventually, factorials will catch up, similar to how exponentials catch up to quadratics.
Luckily I’ve only ever seen this complexity come up in the context of permutations, but because it’s fundamentally different from exponentials it’s worth illustrating that clearly.
Let’s look at all the permutations of 3 characters, and what happens when you want to add a fourth.
For every previous permutation of size N, there are now N+1 possible places to add a new character, each of which will create a new unique permutation.
Because each previous permutation was unique, you have to repeat this process of introducing the new character in every possible slot.
This is the source of the multiplication. And because the number of slots increases with the size of each permutation, the amount you multiply by is also increasing.
Funnily enough, the factorial function actually pops up in the binomial coefficient formula from earlier, but because it’s both in the numerator and denominator it actually kind of cancels itself out.
But the key takeaway to factorials and what differentiates them from exponentials is that changing of the amount you’re multiplying by. And that is precisely what makes them so nightmarishly inefficient.
Just to give you a sense of quickly factorials grow, here are the first 20:
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
13!=6227020800
14!=87178291200
15!=1307674368000
16!=20922789888000
17!=355687428096000
18!=6402373705728000
19!=121645100408832000
20!=2432902008176640000You very quickly run into the issue that computers can’t actually store numbers large enough to deal with factorials.
So if you want to have some fun with a challenging problem involving factorials I’d suggest you try:
Conclusion
Just to wrap things up, I want to leave you with a chart that I think nicely illustrates the differences between quadratic, exponential, and factorial functions. If you’re familiar at all with calculus, we’re essentially just looking at a discrete version of the rate of change for each of these functions.
What you’re looking at is the amount of additional work your algorithm needs to perform for a given input size of N. Notice the difference in operation (addition vs multiplication) and how the amount you add or multiply by changes with larger inputs.
Quadratic functions grow by adding an increasing amount.
Exponential functions grow by multiplying by a constant amount.
Factorial functions grow by multiplying by an increasing amount.
And with that, hopefully, you enjoyed this post and this series on complexity. If you’re looking to challenge yourself further, I’d suggest checking out Outco.io to learn more about their program.
Happy coding!
