Problem : Given an array of nums of distinct integers, return all the possible permutations.

For example, [1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ].

This is my javascript implementation, similar to the standard solution for this problem. I found many places saying this time complexity is to be T(n*n!). But as I understand it should be T((n!)^2). Again I could be wrong !!.

JavaScript Solution

var permute = function(nums) {
    if(nums.length === 0) return [];
    if(nums.length ===1){
        return [[...nums]]; 
    }
    
    let results = [];
    const len = nums.length;
    for(let i=0; i<len; i++){
        // eg: [1,2,3,4]
        const temp = nums[i]; 
        nums[i] = nums[len-1]; 
        nums[len-1] = temp; // [4,2,3,1]
        const n = nums.pop(); // [4,2,3]
        const prems = permute(nums);
        prems.forEach(perm => perm.push(n));
        results = results.concat(prems); 
        nums.push(nums[i]) // [4,2,3,4]
        nums[i] = temp; // [1,2,3,4]
        
    }
    
    return results;
    
 
};

Here is How I got the answer as T((n!)^2)

so for the outer,

1st itteration

• Each iteration will do a recursive call with n-1 items array
• Then the results, which will be all permutations with n-1 items will be size (n-1)!
• So we have to loop through (n-1)! items to append the popped element.

For n itterations

So for the first recursive call, this will happen n times (the outer loop is going from 0 to n)

So, for the first recursive call T-(n*(n-1)!)

Since the recursion tree size is n! the final time complexity should be - T(n!n(n-1)!) = T((n!)^2).

Am I missing something here ??