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

Question

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?

competitive programmer's handbook -- Now they have books written that tell you how to write crazy macros, usage of one-letter variable names, all mushed into one gigantic main function? — PaulMcKenzie
@PaulMcKenzie Haha it's actually surprisingly useful for a complete beginner (such as myself). It's written by Antti Laaksonen and it's free to use. You can find it on Google under the title Competitive Programmer's Handbook — uglygod
Does the book mention how to debug programs? If not, it's just going to encourage more "my program doesn't work, what do I do next?" posts from persons using competitive programming sites. — PaulMcKenzie

Papai from BEKOAIL Papai from BEKOAIL · Accepted Answer · 2020-08-28T05:41:41

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.

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

1 Answers