Time complexity of this code to list all permutations?

Question

For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.

Here is my approach :

#include<stdio.h>
#include<conio.h>
#include<string.h>

void print(char str[],int visited[],int index,char temp[],int len)
{



    if(index==len)
    {
        temp[index]='\0';
        printf("\n%s",temp);
        return;
    }


    for(int i=0;i<len;i++)
    {
        if(!visited[str[i]-'A'])
        {
            visited[str[i]-'A']=1;
            temp[index]=str[i];
            print(str,visited,index+1,temp,len);
            visited[str[i]-'A']=0;
        }
    }


}

int main()
{
    int visited[20]={0};
    char temp[20];
    char str[] = "ABCD";
    int len=strlen(str);
    print(str,visited,0,temp,len);

    getch();
    return 0;
}

I have made use of a visited array to avoid repetition of characters. What will be the complexity of this code?

@Rapptz i am aware of that function. But i wanted to know what the running time of this code is. — nikola
Are you sure you want to tag this as C++? This looks like C to me. — Rapptz
Normally, the complexity of this problem will be n!/(a!)*(b!) ... with a , b, .. is the number of appearances of a specific character in the string. — Pham Trung

templatetypedef templatetypedef · Accepted Answer · 2013-10-11T20:33:14

If you let n be the total number of characters available and k be the number of characters not yet picked, then you can see that each function call does Θ(n) work (either by iterating over the array of length len or by printing out a string of length len), then spawns off k recursive calls. The total work done per call is always Θ(n), so we can count the total work done by looking at how many total calls are made.

Notice that there will be

1 call with k = n,
n calls with k = n - 1,
n(n-1) calls with k = n - 2,
n(n-1)(n-2) calls with k = n - 3,
...
n! / k! calls for arbitrary k

So the total number of calls is given by the sum

sum from k = 0 to n (n! / k!)

= n! (sum from k = 0 to n (1 / k!))

An interesting observation is that the summation here is the Taylor expansion for e (1/0! + 1/1! + 1/2! + 1/3! + ... ), truncated a bit early. Therefore, as n gets large, the number of calls made asymptotically approaches e n!. It's also lower-bounded by n!, so this summation is Θ(n!). Since you're done Θ(n) work per call, the total amount of work done is therefore Θ(n · n!).

Hope this helps!

Time complexity of this code to list all permutations?

2 Answers