Generate All Permutations Time Complexity?


#1

Hello there,

This problem is not from the book, but something that I was trying to solve after seeing permutation related questions. Basically, I want to generate all possible permutations from a list of integers. I have a recursive solution like below which is a pretty general approach to this question I think.

public void subPermute( List<List<Integer>> permutationLists, int start, int[] nums ) {
    //base
    if ( start == nums.length ) {
        final List<Integer> permutation = new ArrayList<Integer>();
        for ( int num: nums ) {
            permutation.add( num );
        }
        permutationLists.add( permutation );
    }
    
    for ( int i = start ; i < nums.length ; i ++ ) {
        swap( nums, start, i );
        subPermute( permutationLists, start + 1, nums );
        swap( nums, start, i );
    }
}

Basically, I’m taking turn to each element in the list the first position and after fixing that first position, I’m permuting the rest of the list recursively until there is only one element to permute in the list.

I have heard varying answers to the time complexity of the above general approach. I believe that the recurrence equation to the above should be T(n) = nT(n-1) + O(n) where O(n) comes from swapping in the for loop. I have tried to solve this by drawing out a recurrence tree, where there will be n! leaf nodes, each of which has n operations. The depth of the tree I think will be n.

Do you guys agree with the recurrence equation? What would be the time complexity of the recurrence equation if you do agree?

Thanks in advance!