All permutations of a given string - complexity

Question

I wrote this solution of the all permutations of string. I have a question about time and space complexity of this solution. I am assuming that time complexity will be O(n³) since nested loop and recursion and space complexity will be O(n) because of recursion.

Is my assumption correct? If so, is there any better performance solution?

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Input: "ABC"

Output: [ 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA' ]

Thanks!

function permutation(string) {
    // Basecase
    if (string.length < 2) {
      return string; 
    }

    var permutations = []; // This array will hold our permutations

    for (var i = 0; i < string.length; i++) {
        var char = string[i];

        // Cause we don't want any duplicates:
        // if char is not matched, skip it this time
        // otherwise it will generate duplicated string 
      
        if (string.indexOf(char) != i) { 
          continue;           
        }
       
        var remainingString = string.slice(0,i) + string.slice(i+1,string.length);  
        var tempResult = permutation(remainingString) 
        for (var subPermutation of tempResult) {
            var result = char + subPermutation
            permutations.push(result)
        }
    }
  
    return permutations;
}

console.log(permutation('ABC'))

Eric · Accepted Answer · 2018-03-28 22:02:14Z

4

There exists O(n!) permutations of a string of length n.

In generating each string in the permutation, you are doing O(n) operation by having a for loop of O(string.length) = O(n)

It might not be obvious why there's n!, but you are recursively calling permutation(..) function with remaining string, so the string length will be n * (n - 1) * (n - 2) * (n - 3) * ... * 1.

Thus, the time complexity of your algorithm is O(n * n!).

Other popular known solutions (swap-based, which is similar to yours, and next-permutation-based) have the same time complexity.

answered Mar 28, 2018 at 22:02

Eric

2,7257 gold badges32 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

All permutations of a given string - complexity

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related