Explain time complexity of permutations using the mathematical expression

This is my code for computing all the permutations for the input array.

public class Permutations {
    public static void main(String[] args) {
        int[] a = {3, 1, 4};
        permutations(a, new int[a.length], new ArrayList<>());
    }
    
    private static void permutations(int[] a, int[] map, List<Integer> ds) {
        if(ds.size() == a.length) {
            System.out.println(ds);
            return;
        }
        
        for(int i = 0; i < a.length; i++) {
            if(map[i] != -1) {
                ds.add(a[i]);
                map[i] = -1;
                permutations(a, map, ds);
                ds.remove(ds.size()-1);
                map[i] = 0;
            }
        }
    }
}

I wanted to know the time complexity for this program, so, I decided to solve it using mathematical expression:

T(n) = n*T(n-1)
     = n*[(n-1)*T(n-2)]
     = n*(n-1)*(n-2)*--*T(0)
     = n!

So, I got n! using my mathematical expression, but I see more number of recursive calls going on in recursive tree.

For n = 3, n!= 6 where as recursive tree has 15 recursive calls.

Help me how in solving the time complexity correctly using mathematical expression.

Solution

Your mathematical analysis only counts the leaves of the recursion tree.

To count each recursive call, you need to add 1 to account for the current call. So for the deepest call we have 𝑇(0) = 1, and for the top-level call we have:

𝑇(𝑛) = 1 + 𝑛𝑇(𝑛−1)
𝑇(𝑛) = 1 + 𝑛(1 + (𝑛−1)𝑇(𝑛−2))
...
𝑇(𝑛) = 1 + 𝑛 + 𝑛(𝑛−1) + 𝑛(𝑛−1)(𝑛−2) + ... + 𝑛!

For 𝑛=3 this is 1 + 3 + 6 + 6 = 16, which matches what you found in your drawing.

Note however that the count of recursive calls is in this case not the whole story for determining the time complexity: Each time the for loop executes, it iterates the complete a array, so that represents O(𝑛) work no matter how many times the if condition is false.

This means that in terms like (𝑛−1)𝑇(𝑛−2) we only count the work done in the if block (which executes 𝑛−1), but don't account for the loop overhead that makes 𝑛 iterations, so this term should not be 1+(𝑛−1)𝑇(𝑛−2), but 𝑛+(𝑛−1)𝑇(𝑛−2).

In short all terms should have their "1+" replaced with "𝑛+":

𝑇(𝑛) = 𝑛 + 𝑛(𝑛 + (𝑛−1)𝑇(𝑛−2))
𝑇(𝑛) = 𝑛 + 𝑛(𝑛 + (𝑛−1)(𝑛 + (𝑛−2)𝑇(𝑛−3)))
...
𝑇(𝑛) = 𝑛 + 𝑛² + 𝑛²(𝑛−1) + 𝑛²(𝑛−1)(𝑛−2) + ... + 𝑛𝑛! + 𝑛!

The most significant term is 𝑛𝑛!