Search code examples
javaalgorithmrecursiontime-complexitypermutation

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


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(n2 * 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 branchesdepth, to estimate the number of nodes in the recursion tree, I get nn nodes in the recursion tree, which is quite different from n * n!.

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


Solution

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

    enter image description here

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