Big O Notation: O(N!)

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(2^N), O(n²), 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(2^N). 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(2^N). However, it gets worst as N increases. Watch what happens to the number of iterations required for both functions as N increases.

O(2^N) :

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(2^N) 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 2^N, 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

Comments

[Steve Geluso]

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!

[Joseph Trettevik]

Thanks, Steve! I was surprised by how much worse N! was as well. Doing the research for this post was really fun.