How to estimate the Time Complexity of generating string Permutations using Recursion tree

Question

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.

The number of branches correlates with the current recursion depth; their sum is constant. So there is really only one variable, and it's easy to see that n! is an accurate count of the number of calls. As a first approximation to an answer, you shouldn't use `branch**depth` unless they are both constant throughout the recursion. — rici, Apr 06 '22 at 15:32

Alexander Ivanchenko · Accepted Answer · 2022-04-06T20:10:31.127

Recursion Call Tree

The formula branches ^ depth is applicable for time-complexity analysis when each recursive call spawn the same number of branches. Like, for instance, a recursive implementation for N'th Fibonacci sequence member. Where every call either terminates or creates exactly 2 new branches of execution and the time complexity will be O(2^n).

The tree of recursive method calls for the code listed in the question is shown below (remained characters on the left, prefix is on the right).

As you can see, the number of branches decreases from top to bottom (from n to 1), because the number of characters hasn't been used yet decreases.

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!).

I appreciate you explaining the intuition behind why the number of permutations is O(n^2*n!). However, I was more curious about how I could derive this information by drawing the recursion tree. — Warren Crasta, Apr 06 '22 at 18:35

score 0 · Answer 2 · answered Apr 06 '22 at 18:47

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!).

How to estimate the Time Complexity of generating string Permutations using Recursion tree

2 Answers2

Recursion Call Tree

Permutations

Algorithm - costs of operations