loading...
Cover image for Big O Notation: O(N!)

Big O Notation: O(N!)

lofiandcode profile image Joseph Trettevik Updated on ・4 min read

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!

Gif of the Archer version of the motorcycle scene from Top Gun
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

Gif of the Archer version of classroom scene from Top Gun

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,
Diagram showing all the nodes in the tree
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

Gif of the Archer version of Goose and Maverick High Five scene from Top Gun

  • 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

Posted on by:

lofiandcode profile

Joseph Trettevik

@lofiandcode

Full Stack Software Engineer who loves puzzles. Experience in React, JavaScript, and Ruby on Rails, and strong skills in problem solving and writing algorithms.

Discussion

pic
Editor guide
 

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.