CODEWITHSUNDEEP
calgorithmtime-complexity
user1213495
user1213495

Reputation: 31

How to calculate the time complexity of back tracking algorithm

Have used this program, How to calculate the time complexity of a backtracking algo?

/*
  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 swap (char *x, char *y)
{
  char temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

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
    }
  }
}

Upvotes: 3

Views: 5030

Answers (2)

Chee Loong Soon
Chee Loong Soon

Reputation: 3727

A simple intuition is that there will be n! permutation and you have to generate all of them. Therefore, your time complexity will be at least n! as you will have to traverse through all n! in order to generate all of them. Thus, the time complexity is O(n!).

Upvotes: 0

amit
amit

Reputation: 178441

Each permute(a,i,n) causes n-i calls to permute(a,i+1,n)

Thus, when i == 0 there are n calls, when i == 1 there are n-1 calls... when i == n-1 there is one call.

You can find from this a recursive formula for number of iterations:
T(1) = 1 [base] ; and T(n) = n * T(n-1) [step]

Resulting in total of T(n) = n * T(n-1) = n * (n-1) * T(n-2) = .... = n * (n-1) * ... * 1 = n!

EDIT: [small correction]: since the condition in the for loop is j <= n [and not j < n], each permute() is actually invoking n-i+1 times permute(a,i+1,n), resulting in T(n) = (n+1) * T(n-1) [step] and T(0) = 1 [base], which later leads to T(n) = (n+1) * n * ... * 1 = (n+1)!.
However, it seems to be an implementation bug more then a feature :\

Upvotes: 12

Related Questions