What will be the complexity of this code?

Question

My code is:

vector<int> permutation(N); vector<int> used(N,0); void try(int which, int what) { // try taking the number "what" as the "which"-th element permutation[which] = what; used[what] = 1; if (which == N-1) outputPermutation(); else // try all possibilities for the next element for (int next=0; next<N; next++) if (!used[next]) try(which+1, next); used[what] = 0; } int main() { // try all possibilities for the first element for (int first=0; first<N; first++) try(0,first); } 

I studied complexity from some website where I came across this code. In my understanding, the next line is repeated N times. Thus, the complexity is O (N).

 for (int first=0; first<N; first++) 

Next, I look at a recursive call.

 for (int next=0; next<N; next++) if (!used[next]) try(which+1, next); 

Thus, this recursive call has a number of steps: t (n) = Nc + t (0) (where is some constant step) There we can say that for this step the complexity is = O (N).

So the overall complexity is O (NN) = O (N ^ 2)

As far as I understand? Thank you

Answer 1

The complexity of this algorithm is O (N!) (Or even O (N! * N) if outputPermutation accepts O (N), which seems possible).

This algorithm outputs all permutations of 0..N natural numbers without repetition.

The recursive function try itself sequentially tries to put N elements in the position which and for each try it recursively calls itself for the next position which , until which reaches N-1. In addition, for each iteration, try is actually called (N - which ) times, because at each level some element is marked as used to eliminate repetition. Thus, the algorithm takes N * (N - 1) * (N - 2) ... 1 step.

Answer 2

This is a recursive function. The try function calls itself recursively, so there is a loop in main (), a loop in try (), a loop in a recursive call to try (), a loop in the next recursive call to try (), etc. on the.

You need to carefully analyze what this function does, or you will get a completely wrong result (like you). You might consider running this code with values ​​from N = 1 to 20 and measuring time. You will see that this is definitely not O (N ^ 2). Actually, do not skip any of the N values; you will understand why.