order of recursion in c

Question

I have written a program to print all the permutations of the string using backtracking method.

# include <stdio.h>
/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
              swap((a+i), (a+j));
              permute(a, i+1, n);
              swap((a+i), (a+j)); //backtrack
           }
   }
} 

/* Driver program to test above functions */
int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}

What would be time complexity here.Isn't it o(n²).How to check the time complexity in case of recursion? Correct me if I am wrong.

Thanks.

Answer 1

The complexity is O(N*N!), You have N! permutations, and you get all of them.
In addition, each permutation requires you to print it, which is O(N) - so totaling in O(N*N!)

Answer 2

My answer is going to focus on methodology since that's what the explicit question is about. For the answer to this specific problem see others' answer such as amit's.

When you are trying to evaluate complexity on algorithms with recursion, you should start counting just as you would with an iterative one. However, when you encounter recursive calls, you don't know yet what the exact cost is. Just write the cost of the line as a function and still count the number of times it's going to run.

For example (Note that this code is dumb, it's just here for the example and does not do anything meaningful - feel free to edit and replace it with something better as long as it keeps the main point):

int f(int n){ //Note total cost as C(n)
  if(n==1) return 0; //Runs once, constant cost
  int i;
  int result = 0; //Runs once, constant cost
  for(i=0;i<n;i++){
    int j;
    result += i; //Runs n times, constant cost
    for(j=0;j<n;j++){
      result+=i*j; //Runs n^2 times, constant cost
    }
  }
  result+= f(n/2); //Runs once, cost C(n/2)
  return result;
}

Adding it up, you end up with a recursive formula like C(n) = n^2 + n + 1 + C(n/2) and C(1) = 1. The next step is to try and change it to bound it by a direct expression. From there depending on your formula you can apply many different mathematical tricks.

For our example:

For n>=2: C(n) <= 2n^2 + C(n/2)

since C is monotone, let's consider C'(p)= C(2^p): C'(p)<= 2*2^2p + C'(p-1)

which is a typical sum expression (not convenient to write here so let's skip to next step), that we can bound: C'(p)<=2p*2^2p + C'(0)

turning back to C(n)<=2*log(n)*n^2 + C(1)

Hence runtime in O(log n * n^2)

Answer 3

The exact number of permutations via this program is (for a string of length N)

• start : N p. starting each N-1 p. etc...
• number of permutations is N + N(N-1) + N(N-1)(N-2) + ... + N(N-1)...(2) (ends with 2 since the next call just returns)
• or N(1+(N-1)(1+(N-2)(1+(N-3)(1+...3(1+2)...))))

Which is roughly 2N!

Adding a counter in the for loop (removing the printf) matches the formula

• N=3 : 9
• N=4 : 40
• N=5 : 205
• N=6 : 1236 ...

The time complexity is O(N!)