CODEWITHSUNDEEP
algorithmrecursionbig-otime-complexity
SdSdsdsd
SdSdsdsd

Reputation: 123

Is recursion or stack necessary for factorial time complexity algorithms?

I have a set with elements. I need to generate all the permutations of those elements.

The time complexity of the algorithm that I'm using is O(n!) and it is recursion based. Naturally every recursive algorithm can be converted to non-recursive using an infinite loop and a stack.

Is it possible to generate all the permutations without using either recursion or the stack + loop equivalence ?

Upvotes: 0

Views: 233

Answers (2)

AbcAeffchen
AbcAeffchen

Reputation: 15017

As answerd before:
No, recursion and stack are not necessary for factorial time complexity algorithms.

But as I read your post, it looks like you want to ask instead

Is it possible to generate all permutations of n elements faster than O(n!)?

The answer to that is also: no.

Since there are n! different permutations of n elements, every algorithm that saves or displays or does anything with all n! permutations, requires at least O(n!) time. This includes generation of the permutations.

Upvotes: 1

Rufflewind
Rufflewind

Reputation: 8966

The answer to

Is recursion or stack necessary for factorial time complexity algorithms

in general is no, trivially. Take for example a code that simply iterates through all numbers from 1 to n!:

for i from 1 to factorial(n):
    play("ni.mp3")

As for

Is it possible to generate all the permutations without using either recursion or the stack + loop equivalence ?

the answer is yes and you can find the answer here. There are several different vraiations available depending on the order that you'd like them to be generated. Here's an example from the first answer:

You start from the rightmost number and go one position to the left until you see a number that is smaller than its neighbour. Than you place there the number that is next in value, and order all the remaining numbers in increasing order after it. Do this until there is nothing more to do. Put a little thought in it and you can order the numbers in linear time with respect to their number.

Upvotes: 1

Related Questions