What is the performance in Big-O notation of the following algorithm? It's a function I wrote to print all permutations of a string. I know for an input of length n there are n! different permutations. Can somebody provide an explanation of the analysis made to reach such conclusions?

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void permute(char* output, char* input, int used[], int index, int length){
int i;
if (index == length) {
printf("%s\n", output);
return;
}
for (i=0; i< length; i++){
if (! used[i] ){
output[index] = input[i];
used[i] = 1;
permute(output, input, used, index+1, length);
used[i] = 0;
}
}
}
int main(){
char input[] = "abcd";
char* output;
int length = strlen(input);
int* used;
// Allocate space for used array
used = (int*) malloc (sizeof (int)* length);
memset (used, 0, sizeof (int)* length);
// Allocate output buffer
output = (char*) malloc ( length+1);
if (!output) return 1;
output[length] = '\0';
// First recursive call
permute(output, input, used, 0, length);
free (output);
return 0;
}
```

I would say O(n!), since every recursion does a loop with n rounds and calls something on an object of "size" n-1 (since used[i] has masked out one character).

I know for an input of length n there are n! different permutations.

You just answered your own question

Similar Questions

I've come across some code that looks something like this: foo = r Hello How are you Goodbye Is this convention just an easy way to keep the formatting of the string that could cause problems

I want to invert the order of a string. For example: Joe Red = Red Joe I believe the reverse method will not help me, since I dont want to reverse every character, just switch words

i am trying to generate all the permutations of a given string. the logic im using suppose string =abcd 1) then i fix 'a'(and similarly each character.. first iteration - abcd, second-bacd, third-cab

I am looking for a fast algorithm for search purpose in a huge string (it's a organism genome sequence composed of hundreds of millions to billions of chars). There are only 4 chars {A,C,G,T} present

I came across this question on an interview website - We are given 4 numbers say n1, n2, n3, n4. We can place them in any order and we can use the mathematical operators +, -, *, / in between them to

Which algorithm for permutation of list is predictable? For example, i can get number of i-th permutation (Haskell code) --List of all possible permutations permut [] = [[]] permut xs = [x:ys|x<-x

Here is a function that iterates over permutations of letters in a string: def permutations(items): for x in _permutations_rec('', items, len(items)): yield x def _permutations_rec(current, items, n):

Can someone please explain algorithm for itertools.permutations routine in Python standard lib 2.6? I see its code in the documentation but don't undestand why it work? Thanks Code is: def permutation

How to convert a double into a floating-point string representation without scientific notation in the .NET Framework? Small samples (effective numbers may be of any size, such as 1.5E200 or 1e-200)

I saw this in an interview question , Given a sorting order string, you are asked to sort the input string based on the given sorting order string. for example if the sorting order string is dfbcae an

How do I build an escape sequence string in hexadecimal notation. Example: string s = \x1A; // this will create the hex-value 1A or dec-value 26 I want to be able to build strings with hex-values b

I'm looking for an algorithm that takes as arguments two strings, source and destination, and returns the steps required to transform the source string to the destination. Something that takes Levensh

Ok, these are all pretty simple methods, and there are a few of them, so I didnt want to just create multiple questions when they are all the same thing. BigO is my weakness. I just cant figure out ho

Inspired by this question and answer, how do I create a generic permutations algorithm in F#? Google doesn't give any useful answers to this. EDIT: I provide my best answer below, but I suspect that T

I've found a way to convert a math expression in infix notation into postfix notation. (http://en.wikipedia.org/wiki/Shunting-yard_algorithm) But then, how should I code to interpret the result expres

I'm looking for an Algorithm (Preferably with a java implementation) for merging Strings. my problem is as following : suppose I have an Array/List of Strings {myString1 , my String1 , my-String-

This is a problem on Asymptotic Notation from the assignment of MIT OpenCourse Introduction to Algorithm: For each of the following statements, decide whether it is always true, never true, or sometim

I am currently working on a simple function that will scramble an inputted string where all possible permutations are equally likely. My code is below. function scramble(s) { result = s.split(); for

I'm looking for the name of a certain kind of algorithm, which I think should have a name. The algorithm is the one that figures out the shortest possible string in order to make it identifiably uniqu

First, here is my code for the O(n): import java.util.*; public class BigO{ public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print(Enter a number: ); String u

public class Convert{ /* the algorithm works as follows after inserting all elements of infix string into an empty Queue iterate over queue for infix.length() number of times and check if element at f

I've seen this Rabin Karp string matching algorithm in the forums on the website and I'm interested in trying to implement it but I was wondering If anyone could tell me why the variables ulong Q and

EDIT: I want to use a .py file like a config file. So using the {...} notation i can create a dictionary using string as keys but the definition order is lost in a standard python dictionary. My quest

I'm using the Blowfish algorithm for encrypting passwords in my application. After reinstalling Ubuntu on the server, the output of this algorithm has changed - though I'm trying the same string and t

Sometimes I get totally fooled trying to estimate an algorithm's speed with the O(x) notation, I mean, I can really point out when the order is O(n) or O(mxn), but for those that are O(lg(n)) or O(C(p

I'm a little bit confused. How is the problem of generating permutations in Lexicographic Order any different from the problem of sorting? Can someone please explain it to me with an example? Thanks

I have a string of letters that I'd like to split into all possible combinations (the order of letters must be remain fixed), so that: s = 'monkey' becomes: combinations = [['m', 'onkey'], ['mo', 'nk

In java, I'm trying to find a way to generate permutations based on restrictions. How can I generate the number of permutations (with the restrictions in mind), or at least know how many? Edit: Simple

I am trying to solve this challenge on InterviewStreet: https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd I already have a working algorithm but I would to improve its perfor

Can you give me an algorithm to print all permutations of a string, with no duplicates, both recursively and iteratively?

i need help finding time complexity of this function in big O notation: int myfunction(bool exists) { int var=0; int k,j,n; if (exists) for(k=1; k<=n; k*=2) for(j=1; j<=k; j++) var++; else for(k

I'm trying to use qsort to sort a string of characters alphabetically. At the moment it just seems to be reversing the order of my string. printf(unsorted %s\n, string); qsort(string, strlen(string

I know you can generate all permutations from a list, using glob or Algorithm::Permute for example - but how do you generate all possible permutations from a regular expression? I want to do like: @pe

I'm trying to generate k-permutations (variations) in lexicographical (alphabetical) order. For example, this code import itertools a = list('ABCD') k = 2 for c in itertools.combinations(a, k): for p

Is big-O notation a tool to do best, worst, & average case analysis of an algorithm? Or is big-O only for worst case analysis, since it is an upper bounding function?

Is there any way to use permutations in htaccess for RewriteRule ? For example I have this url: http://localmachine/index.php?c=category&brand=mybrand&country=mycountry&offer=yes&new=

I would like to generate permutations of string words that are inputted from a file. I know the count and was wondering if there is an easy way to do this using an arraylist.

Is there a simple algorithm, given a depth vector (ie the one going into the screen) to determine which polygon (or rather, just which triangle) is 'behind' the other one from their coordinates so I c

I'm trying to take a seven-character string and generate all the possible 3- and 4-letter permutations of it. This seems like something that recursion would be handy for (most all permutation generato

I want to get all the 3 letter permutations possible from every letter in the alphabet using itertools. This comes back blank: import itertools def permutations(ABCDEFGHIJKLMNOPQRSTUVWXYZ, r=3): pool

I am searching for an algorithm to compare two strings efficiently without occupying much memory and in less time. So what I am currently doing is, compressing character string first and then comparin

Is there any way to serialize BigInteger field in plain format as String JavaScript object field, rather than Numeric in exponential notation (which is default behavior of Jackson)?

Generally, programs which evaluate an infix mathematical expression use some variation of the Shunting Yard Algorithm to first translate the expression into Reverse Polish Notation, and then evaluate

In Wolfram Mathematica，there is a function called Permutations(http://reference.wolfram.com/mathematica/ref/Permutations.html). It can gives all permutations containing exactly n elements. For example

I would like to access the object provided only it's string path in form of array is known. 1.) there is an object, where root[obj1][obj2] = 1; (in common case root[obj1]...[objN]) 2.) I have

Is the default sort order an implementation detail? or how is it that the Default Comparer is selected? It reminds me of the advice. Don't store HashCodes in the database Is the following Code guara

There is a set e.g.(1, 4, 2, 5, 7, 6, 9, 8, 3). We calculate its first difference (FD) the following way: firstDifference[i] = inputArray[i+1] - inputArray[i]. inputArray is original set. In example c

I am looking for a simple and FAST algorithm to encrypt/decrypt a string (length is about 128 bytes) with a password. Any good algorithms? ADDED: Custom algorithm is absolutely OK. Less memory it take

If we have a source string and encrypted string, can we find out algorithm/forumla used in encrypting that source string? EDIT Here are a couple of such strings. string, encrypted string avtacarguy,c0

I need to check whether my CString object in MFC ends with a specific string. I know that boost::algorithm has many functions meant for string manipulation and that in the header boost/algorithm/strin