What is the time complexity of this code that generates the permutations of a set?

user_11612118 0
Viewed 86

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?

time-complexity algorithm c++
1 Answers

It is still: O(N*N!)

To process permutation requires O(N) time and there should be total N's factorial permutate value so it requires O(N!).

Therefore total complexity lies in O(N*N!)

Note: push_back() and pop_back() requires constant time O(1) time.

user_83596230
Related