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?

Source: Windows Questions C++