Find time complexity

Question

void permute(string elems, int mid, int end)
{
    static int count;
    if (mid == end) {
        cout << ++count << " : " << elems << endl;
        return ;
    }
    else {
    for (int i = mid; i <= end; i++) {
            swap(elems, mid, i);
            permute(elems, mid + 1, end);
            swap(elems, mid, i);
        }
    }
}

How to derive recurrence relation from the above code and what will be the time complexity?

Answer 1

Given algorithm is  all permutations of a given string.

Suppose You have  String ABC

Then the permutations of string ABC.

ABC ACB BAC BCA CBA CAB

Recurrence relation=n*T(n-1)+n

Time Complexity: O(n*n!)

Comments

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

---

Time complexity is $O(n!)$ or $O((n+1)!)$?

---

should be O(n!)