Question

What is the time complexity (Big-O) of the following code?

class Main
{
   // Recursive function to generate all permutations of a String
   private static void permutations(String candidate, String remaining)
   {
       if (remaining.length() == 0) {
           System.out.println(candidate);
       }

       for (int i = 0; i < remaining.length(); i++)
       {
           String newCandidate = candidate + remaining.charAt(i);

           String newRemaining = remaining.substring(0, i) +
                               remaining.substring(i + 1);

           permutations(newCandidate, newRemaining);
       }
   }

   // Find Permutations of a String in Java
   public static void main(String[] args)
   {
       String s = "ABC";
       permutations("", s);
   }
}

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The program basically prints the permutation of string.

So,

Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.

Kindly revert for any queries

Thanks.