I've read the following code in the competitive programmer's handbook where search
processes all of the permutations of a set that contains the elements {0,1,..., n-1}
:
void search() {
if (permutation.size() == n) {
// process permutation
} else {
for (int i = 0; i < n; i++) {
if (chosen[i]) continue;
chosen[i] = true;
permutation.push_back(i);
search();
chosen[i] = false;
permutation.pop_back();
}
}
}
There is a vector called permutation
that contains the current elements in the permutation and an array called chosen
that keeps track of which elements have already been chosen.
I understand the how the code runs, but I am struggling to understand its time complexity. I know there are n!
final permutations, but it appears as though the for
loop is executed more times than this. Take for example the following picture:
The for
loop is executed at each node. What exactly is the time complexity of the above code?
main
function? – PaulMcKenzie