complexity of recursive string permutation function

Question

From: Are there any better methods to do permutation of string?

what is the complexity of this function???

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

score 26 · Accepted Answer · answered Mar 19 '11 at 19:51

26

Ignoring the print, the recurrence relation satisfied is

T(n) = n*T(n-1) + O(n)

If G(n) = T(n)/n! we get

G(n) = G(n-1) + O(1/(n-1)!)

which gives G(n) = Theta(1).

Thus T(n) = Theta(n!).

Assuming that the print happens exactly n! times, we get the time complexity as

Theta(n * n!)

answered Mar 19 '11 at 19:51

@rajyavardhan: Why is there an `O(n)` factor in the initial recurrence? – crisron Mar 21 '16 at 19:12
Because of the swap operations - each operation takes O(1) and that happens in a loop. – Parth Thakkar Nov 23 '16 at 16:26
Is the space complexity also quadratic `O(n^2)` because the unique permutations stored in a Set would grow larger the greater the initial input? – AdamHurwitz Nov 02 '20 at 01:37

MAK · Answer 2 · 2011-03-20T06:06:43.033

8

Without looking too deeply at your code, I think I can say with reasonable confidence that its complexity is O(n!). This is because any efficient procedure to enumerate all permutations of n distinct elements will have to iterate over each permutation. There are n! permutations, so the algorithm has to be at least O(n!).

Edit:

This is actually O(n*n!). Thanks to @templatetypedef for pointing this out.

edited Mar 20 '11 at 06:06

answered Mar 19 '11 at 18:29

MAK

26,140
11
55
86

1

I think you're forgetting the O(n!) times you're printing O(n) characters, which takes O(n x n!) time. – templatetypedef Mar 19 '11 at 19:58
@templatetypedef: n*n!<(n+1)*n!, i.e. n*n!<(n+1)!. O((n+1)!) is the same as O(n!), the extra n does not matter. – MAK Mar 19 '11 at 20:31
6

@MAK- O(n!) != O((n+1)!). It's true that anything that's O(n!) is also O((n+1)!), but the opposite doesn't hold. A quick proof - (n+1)! = O((n+1)!) trivially. Now suppose that (n+1)! = O(n!); then there must be some c, n0 such that for any n > n0, (n+1)! < c n!. This would mean that for any n > n0, n < c, which is impossible for any constant c. – templatetypedef Mar 19 '11 at 20:35

score 3 · Answer 3 · answered Mar 19 '11 at 17:37

3

long long O(int n)
{
    if (n == 0)
        return 1;
    else 
       return 2 + n * O(n-1);
}

int main()
{
    //do something
    O(end - mid);
}

This will calculate complexity of the algorithm.

Actualy O(N) is N!!! = 1 * 3 * 6 * ... * 3N

answered Mar 19 '11 at 17:37

Mihran Hovsepyan

10,810
14
61
111

complexity of recursive string permutation function

3 Answers3

Linked