The following code prints all permutations of a string:

void permutation(String str) {
    permutation(str, "");
}
    
void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i  ) {
            String rem = str.substring(0, i)   str.substring(i   1);
            permutation(rem, prefix   str.charAt(i));
        }
    }
}

GeeksForGeeks analyzes the time complexity of the code by determining:

• the function gets called n! times in its base case
• the for-loop runs n times
• as a result, there will be no more than n * n! factorial nodes in the recursion tree.
• each function call corresponds to O(n) work, therefore the total time complexity is O(n² * n!).

I know that the time complexity can be estimated by multiplying the number of nodes in the recursion tree by the amount of work each function call does. If I use the formula branches^depth, to estimate the number of nodes in the recursion tree, I get nⁿ nodes in the recursion tree which is quite different from n * n!.

I'd like to know why branches^depth isn't a tight bound for this problem and in which cases I shouldn't use O(branches^depth) to estimate the time complexity of a function that makes multiple calls.

CodePudding user response：

Permutations

The number of permutations of the given String of length n is n!.

Let's explore why with a simple example.

Imagine that you need to pick 1 card from the standard deck of cards of size 52. I.e. there are 52 possibilities to chose from.

After the first card has been picked, you need to choose the next one, and there's a 51 way to make this choice.

That means that the total number of ways of how 2 cards can be picked is 52*51.

Then for the third card we have only 50 cards remaining in the deck.

That means that there are 52*51*50 ways to choose 3 cards from the deck.

For four cards, that number will be 52*51*50*49, for five - 52*51*50*49*48, and so on.

That is a so-called proof by induction that there are 52*51*50*49*48*...*3*2*1 (and that is a factorial - 52!) ways to pick 52 cards from the deck.

Now, you might think of each character in a string as if it's a card and the string itself is a deck of size n. Similarly, there will be n! way to pick all n characters from this string.

Algorithm - costs of operations

Since the number of permutations is n! that means that we need to generate n! strings of length n.

Each string has to be constructed letter by letter:

prefix   str.charAt(i) // append a charactor at position `i` to the `prefix` string

In order to create a string of length n, we need to pick a character n times in a loop. Each step of iteration will spawn a recursive method call. Therefore, n*n! method calls will be required to construct all n! permutations.

There's an additional cost that contributes to the total time complexity.

Creation of the remaining string (characters that are not picked yet) requires to invoke

str.substring(0, i)   str.substring(i   1)

at each method call. And that will cost O(n) time because in order to create a substring we have iterated over the source string and copy up to n - 1 characters from its underlying array into the new string.

Therefore, the overall time complexity will be O(n^2*n!).

CodePudding user response：

As @rici suggested in the comments, branches^depth doesn't seem to be a good estimation when the number of branches for a node varies based on the recursion depth, as seen in this problem.

For this problem, it seems that a better way to estimate the number of nodes is to use the formula described by @Shubham here:

Complexity = length of tree from root node to leaf node * number of leaf nodes

When I draw the recursion tree of this function for a string of length n, I see that there are n! leaf nodes. The depth of the recursion is n, so the total number of nodes is n * n!. As mentioned in the question, since each function call corresponds to O(n) work, therefore the total time complexity is O(n² * n!).