Time Complexity of permutation function

Question

Given a collection of distinct numbers, return all 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] ]

My Iterative Solution is :

public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int i=0;i<nums.length;i++)
        {
            List<List<Integer>> temp = new ArrayList<>();
            for(List<Integer> a: result)
            {
                for(int j=0; j<=a.size();j++)
                {
                    a.add(j,nums[i]);
                    List<Integer> current = new ArrayList<>(a);
                    temp.add(current);
                    a.remove(j);
                }
            }
            result = new ArrayList<>(temp);
        }
        return result;
    }

My Recursive Solution is:

public List<List<Integer>> permuteRec(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        makePermutations(nums, result, 0);
        return result;
    }


void makePermutations(int[] nums, List<List<Integer>> result, int start) {
    if (start >= nums.length) {
        List<Integer> temp = convertArrayToList(nums);
        result.add(temp);
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);
        makePermutations(nums, result, start + 1);
        swap(nums, start, i);
    }
}

private ArrayList<Integer> convertArrayToList(int[] num) {
        ArrayList<Integer> item = new ArrayList<Integer>();
        for (int h = 0; h < num.length; h++) {
            item.add(num[h]);
        }
        return item;
    }

According to me the time complexity(big-Oh) of my iterative solution is: n * n(n+1)/2~ O(n^3)
I am not able to figure out the time complexity of my recursive solution.
Can anyone explain complexity of both?

The number of permutations for n elements is n!, so an algorithm to produce all n! permutations would have time complexity O(n!). — rcgldr
@OJASJUNEJA yes. It is the best conceivable runtime for this problem. Imagine if you have a magic generator that just spits out a permutation every 1 second. You would still need to wait n! seconds for this generator to finish because there are n! permutations. — nem035
The method doesn't matter. For n sufficiently greater than k, then n! > k^n, so the time complexity is O(n!). One of the few expressions greater than n! is a double exponential, like n^(n^n). — rcgldr
The complexity is O(n!) == O(n**(n + 1/2)*exp(-n)) see en.wikipedia.org/wiki/Stirling's_approximation — Dmitry Bychenko

user1952500 user1952500 · Accepted Answer · 2017-01-13T07:03:09

The recursive solution has a complexity of O(n!) as it is governed by the equation: T(n) = n * T(n-1) + O(1).

The iterative solution has three nested loops and hence has a complexity of O(n^3).

However, the iterative solution will not produce correct permutations for any number apart from 3.

For n = 3, you can see that n * (n - 1) * (n-2) = n!. The LHS is O(n^3) (or rather O(n^n) since n=3 here) and the RHS is O(n!).

For larger values of the size of the list, say n, you could have n nested loops and that will provide valid permutations. The complexity in that case will be O(n^n), and that is much larger than O(n!), or rather, n! < n^n. There is a rather nice relation called Stirling's approximation which explains this relation.

Time Complexity of permutation function

3 Answers