CODEWITHSUNDEEP
algorithmrecursionbig-otime-complexitycomplexity-theory
Srijani Ghosh
Srijani Ghosh

Reputation: 4216

What will be the complexity of this code?

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 was learning complexity from some website where I came across this code. As per my understanding, the following line iterates N times. So the complexity is O(N).

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

Next I am considering the recursive call.

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

So, this recursive call has number of step involved = t(n) = N.c + t(0).(where is some constant step) There we can say that for this step, the complexity is = O(N).

Thus the total complexity is - O(N.N) = O(N^2)

Is my understanding right? Thanks!

Upvotes: 5

Views: 102

Answers (2)

Aivean
Aivean

Reputation: 10882

Complexity of this algorithm is O(N!) (or even O(N! * N) if outputPermutation takes O(N) which seems possible).

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

Recursive function try itself sequentially tries to put N elements into position which and for each try it recursively invokes itself for the next which position, until which reaches N-1. Also, for each iteration try is actually invoked (N - which) times, because on each level some element is marked as used in order to eliminate repetitions. Thus the algorithm takes N * (N - 1) * (N - 2) ... 1 steps.

Upvotes: 3

gnasher729
gnasher729

Reputation: 52538

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

You need to analyse very carefully what this function does, or you will get a totally wrong result (as you did). You might consider actually running this code, with values of N = 1 to 20 and measuring the time. You will see that it is most definitely not O (N^2). Actually, don't skip any of the values of N; you will see why.

Upvotes: 0

Related Questions