Big O notation and time complexity part 6

Today I will go over the factorial time and there will be an example as always.

O(n!) — Factorial time:

Factorial is the multiplication of all positive integer numbers less than itself. For instance:

5! = 5 x 4 x 3 x 2 x 1 = 120

This grows fast depending on the input:

20! = 2,432,902,008,176,640,000

An examples of O(n!) factorial runtime algorithm we have the following:

Permutations of a string:

Write a function that computes all the different words that can be formed given a string. E.g.

getPermutations('a') // => [ 'a']
getPermutations('ab') // =>  [ 'ab', 'ba']
getPermutations('abc') // => [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]

A straightforward way to solve this will be to check if the string has a length of 1. If so, return that string since you can’t arrange it differently.

For strings with a length bigger than 1, we could use recursion to divide the problem into smaller problems until we get to the length 1 case. We can take out the first character and solve the problem for the remainder of the string until we have a length of 1.

function getPermutations(string, prefix = '') {
if(string.length <= 1) {
return [prefix + string];
}
return Array.from(string).reduce((result, char, index) => {
const reminder = string.slice(0, index) + string.slice(index+1);
result = result.concat(getPermutations(reminder, prefix + char));
return result;
}, []);
}
getPermutations("a,b")  
the result is: [ 'a,b', 'ab,', ',ab', ',ba', 'ba,', 'b,a' ]

This is all I have on time complexity. Thank you for being part of this series.