Song of The Week
Haha, this isn't really the song of the week, but I couldn't have a Top Gun themed post and NOT embed Danger Zone by the great Kenny Loggins! I put the real song of the week at the bottom.
Danger Zone!
Okay technically we were in the Danger Zone with O(2N), O(n2), and even O(N log N) to certain extent. But O(N!) is really bad. You should definitely avoid writing code that has a time complexity of O(N!).
Now you may be thinking, "How bad can it be?" It's pretty bad. Let's take a look at why.
Suppose you passed an array of length 5 to a function with a time complexity of O(2N). In that case, the number of iterations of the code would be:
2 * 2 * 2 * 2 * 2 = 32
Now suppose you passed that same array to a function with a time complexity of O(N!). The number of iterations would then be:
1 * 2 * 3 * 4 * 5 = 120
In this example, the O(N!) function performed almost 4 times as many iterations as the O(2N). However, it gets worst as N increases. Watch what happens to the number of iterations required for both functions as N increases.
O(2N) :
N | Number of Iterations |
---|---|
6 | 2 * 2 * 2 * 2 * 2 * 2 = 64 |
7 | 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128 |
8 | 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 25 |
9 | 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 512 |
O(N!) :
N | Number of Iterations |
---|---|
6 | 1 * 2 * 3 * 4 * 5 * 6 = 720 |
7 | 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5,040 |
8 | 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40,320 |
9 | 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 = 362,880 |
After only increasing N to 9, the O(N!) function now performs 709 times as many iterations as the O(2N) function! That's crazy, right?! Imagine if N equaled 100, or 1000?
The reason the factoral is increasing at such a faster rate is because while the total is multipled by 2 each time in 2N, the total is multiplied by a number that continues to increase each time in the case of N!.
Basic Example
const nFacRuntimeFunc = (n) => {
for(let i=0; i<n; i++) {
nFacRuntimeFunc(n-1);
}
}
This example function doesn't do any thing other than execute N! times, but that makes it ideal for helping us understand what to look for. If n = 3, then the for loop will make 3 recursive calls and pass in n = 2. Then those calls will make 2 recusive calls, which will both make 1 recusive call.
So,
If N = 4, then the function would create that same tree 4 times and complete 24 iterations of the code. Easy, right? We got this!
If you'd like to see a non-trivial example of an algorithm with a time complexity of O(N!), checkout the brute force solution to the Traveling Salesman Problem. There's a link to this solution under references below.
Takeaways
- Stay off the highway to the Danger Zone.
- Watch for algorithms that make recursive calls from inside a loop that increases it's number of iterations as N increases.
- Checkout the brute force solution to the Traveling Salesman Problem, as well as the best solution. It's pretty interesting.
Real Song of The Week
Sorry, I know the intro to this week's song is a little emo, but it's so good! Hope you like it! :)
References
Images and Gifs:
Cover Image
Archer - Top Gun motorcycle scene gif
Archer - Top Gun classroom scene gif
Archer - Top Gun High Five gif
Technical:
How to Calculate N!
Basic Example of O(N!) function - Stackoverflow
Traveling Salesman Problem - Brute Force Solution
Traveling Salesman Problem - Best Solution
Top comments (2)
Nice write up. I like the super clear examples with the tables showing how 2^N grows compared to N!. It you would have asked me before reading this I don't think I would have known off the top of my head which was worse!
Thanks, Steve! I was surprised by how much worse N! was as well. Doing the research for this post was really fun.