### 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^{2}), 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

Posted on by:

### Joseph Trettevik

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

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.