Time Complexity of permutation function

Time Complexity of permutation function

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> permute(int[] nums) {
        List> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int i=0;i> temp = new ArrayList<>();
            for(List a: result)
            {
                for(int j=0; j<=a.size();j++)
                {
                    a.add(j,nums[i]);
                    List current = new ArrayList<>(a);
                    temp.add(current);
                    a.remove(j);
                }
            }
            result = new ArrayList<>(temp);
        }
        return result;
    }

My Recursive Solution is:
public List> permuteRec(int[] nums) {
        List> result = new ArrayList>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        makePermutations(nums, result, 0);
        return result;
    }


void makePermutations(int[] nums, List> result, int start) {
    if (start >= nums.length) {
        List 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 convertArrayToList(int[] num) {
        ArrayList item = new ArrayList();
        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?

Solutions/Answers:

Answer 1:

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.

Answer 2:

It's the output (which is huge) matters in this problem, not the routine's implementation. For n distinct items, there are n! permutations to be returned as the answer, and thus we have at least O(n!) complexity.

With a help of Stirling's approximation

 O(n!) = O(n^(1/2+n)/exp(n)) = O(sqrt(n) * (n/e)^n)

we can easily see, that O(n!) > O(n^c) for any constant c, that's why it doesn't matter if the implementation itself adds another O(n^3) since

 O(n!) + O(n^3) = O(n!)

References

Loading...