What would be the time complexity for the below recursive code?

Question

The method uses a recursive approach to print every possible combination of a set of letters.

for example input: abc

output:

abc acb bac bca cab cba

Im unsure how to figure the time complexity for the code. I am thinking it is 2^n due to the for loop within the recursive function but unsure how to go about solving

public class WordScrambler {

public static void scrambleLetters(String remainLetters,  // Remaining letters
                                   String scramLetters) { // Scrambled letters
 
    String tmpString;      // Temp word combinations
    int i;                 // Loop index

    if (remainLetters.length() == 0) { // Base case: All letters used
        System.out.println(scramLetters);

    }
    else {
        // Recursive case: move a letter from
        // remaining to scrambled letters
        for (i = 0; i < remainLetters.length(); ++i) {
            // Move letter to scrambled letters
            tmpString = remainLetters.substring(i, i + 1);
            remainLetters = removeFromIndex(remainLetters, i);
            scramLetters = scramLetters + tmpString;

            scrambleLetters(remainLetters, scramLetters);

            // Put letter back in remaining letters
            remainLetters = insertAtIndex(remainLetters, tmpString, i);
            scramLetters = removeFromIndex(scramLetters, scramLetters.length() - 1);
        }
    }
}

// Returns a new String without the character at location remLoc
public static String removeFromIndex(String origStr, int remLoc) {
    String finalStr;      // Temp string to extract char

    finalStr = origStr.substring(0, remLoc);                     // Copy before location remLoc
    finalStr += origStr.substring(remLoc + 1, origStr.length()); // Copy after location remLoc

    return finalStr;
}

// Returns a new String with the character specified by insertStr
// inserted at location addLoc
public static String insertAtIndex(String origStr, String insertStr, int addLoc) {
    String finalStr;      // Temp string to extract char

    finalStr = origStr.substring(0, addLoc);                 // Copy before location addLoc
    finalStr += insertStr;                                   // Copy character to location addLoc
    finalStr += origStr.substring(addLoc); // Copy after location addLoc

    return finalStr;
}

public static void main(String[] args) {
    Scanner scnr = new Scanner(System.in);
    String wordScramble;      // User defined word to scramble

    // Prompt user for input
    System.out.print("Enter a word to be scrambled: ");
    wordScramble = scnr.next();

    // Call recursive method
    scrambleLetters(wordScramble, "");
    System.out.println("counter " + wordcounter);
}

}

Neil · Answer 1 · 2022-11-22T06:39:01.813

This programme has an inherently factorial time complexity in the number of characters in the string because it's outputting all permutations of the characters. Calling the scrambleLetters function T of the remainLetters string has n characters. The base case n = 0, it will output one permutation; otherwise, loop n times. Each loop, separate the letter, call scambleLetters recursively with one letter gone, and then restore. Because removeFromString builds up finalStr each time, I think this will be:

T(n) = { n = 0: 1 } { n > 0: n(n + T(n-1)) }
     = (n)(n-1)T(n-2) + (n)(n-1)^2 + n^2
     = (n)(n-1)(n-2)T(n-3) + (n)(n-1)(n-2)^2 + (n)(n-1)^2 + n^2
     ...

I would say this is bounded by O(n * n!). Here is an experimental trial of time vs string length:

What would be the time complexity for the below recursive code?

1 Answers1