Announcing Stack Overflow Documentation



Sign up and start helping → Learn more about Documentation →

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

Here is my approach :


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




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

    return 0;

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

share|improve this question
std::next_permutation. – Rapptz Oct 11 '13 at 5:21
@Rapptz i am aware of that function. But i wanted to know what the running time of this code is. – nikola Oct 11 '13 at 5:23
Are you sure you want to tag this as C++? This looks like C to me. – Rapptz Oct 11 '13 at 5:30
@phamTrung Can you please explain? – nikola Oct 11 '13 at 5:41
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 Oct 11 '13 at 8:11
up vote 2 down vote accepted

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!

share|improve this answer
thanks for such a nice explanation! also i wanted to ask why does printf take O(n) time to print a string? – nikola Oct 16 '13 at 15:23
@user2549925- Think about the amount of time required to send each character to the screen. The more characters you have, the more time is required to display them. – templatetypedef Oct 16 '13 at 17:36

Running your code and listing the number of print() calls depending on the length of the string to permute, I've got:

n=1 calls=2
n=2 calls=5
n=3 calls=16
n=4 calls=65
n=5 calls=326
n=6 calls=1957
n=7 calls=13700
n=8 calls=109601
n=9 calls=986410
n=10 calls=9864101
n=11 calls=108505112

That looks like "e * n!".

share|improve this answer
Have you try String with duplicate characters? like aabbbccc? – Pham Trung Oct 11 '13 at 9:09
No, I always started with a sorted alphabet string like "ABCDEF". 'No repetition' is mentioned in the question title. – Axel Kemper Oct 11 '13 at 9:13
The visited array is for that purpose , I think :) I guess that the no repetition here means that there is no string that appear twice :) – Pham Trung Oct 11 '13 at 9:16
I have tried "AAB" without success (no output). The procedure seams to be restricted to strings without repeated characters. – Axel Kemper Oct 11 '13 at 10:34
Oh yes, because of his final check index==len, so your answer is correct :D – Pham Trung Oct 11 '13 at 11:04

Your Answer


