Big O Notation: O(N!)
Tags: algorithms, bigo, beginners
Published: 2020-04-13 02:14:45

---series: Big O Notation---
###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.
{% soundcloud https://soundcloud.com/kennyloggins/danger-zone %}

##Danger Zone!
<img src=https://media.giphy.com/media/De5Lfx0LI1SjS/giphy.gif alt="Gif of the Archer version of the motorcycle scene from Top Gun" width=500>
Okay technically we were in the Danger Zone with O(2<sup>N</sup>), O(n<sup>2</sup>), 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<sup>N</sup>). 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<sup>N</sup>). However, it gets worst as N increases. Watch what happens to the number of iterations required for both functions as N increases.

O(2<sup>N</sup>) :

| 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<sup>N</sup>) 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<sup>N</sup>, the total is multiplied by a number that continues to increase each time in the case of N!.

##Basic Example
<img src=https://media.giphy.com/media/82x3ZQtqp9M88/giphy.gif alt="Gif of the Archer version of classroom scene from Top Gun" width=500>
```javascript
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](https://dev-to-uploads.s3.amazonaws.com/i/v84i747il2r6qnhsa6el.jpg)
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
<img src=https://media.giphy.com/media/iByd2dFdFwKn6/giphy.gif alt="Gif of the Archer version of Goose and Maverick High Five scene from Top Gun" width=500>
* 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! :)
{% soundcloud https://soundcloud.com/ineotic/oui-lele-hopeless %}

##References
Images and Gifs:
[Cover Image](https://static.wixstatic.com/media/72b89f_e84ca9f39d834f3088918ecd136d93e0~mv2.jpg/v1/fill/w_742,h_412,al_c,lg_1,q_85/72b89f_e84ca9f39d834f3088918ecd136d93e0~mv2.jpg)
[Archer - Top Gun motorcycle scene gif](https://media.giphy.com/media/De5Lfx0LI1SjS/giphy.gif)
[Archer - Top Gun classroom scene gif](https://media.giphy.com/media/82x3ZQtqp9M88/giphy.gif)
[Archer - Top Gun High Five gif](https://media.giphy.com/media/iByd2dFdFwKn6/giphy.gif)

Technical:
[How to Calculate N!](https://www.mathsisfun.com/numbers/factorial.html)
[Basic Example of O(N!) function - Stackoverflow](https://stackoverflow.com/questions/3953244/example-of-on)
[Traveling Salesman Problem - Brute Force Solution](https://www2.cs.sfu.ca/CourseCentral/125/tjd/tsp_example.html)
[Traveling Salesman Problem - Best Solution](https://www.quora.com/What-is-the-optimal-and-best-algorithm-for-solving-the-traveling-salesman-problem)