What is the time complexity of heaps law of permutations? | Sololearn: Learn to code for FREE!


What is the time complexity of heaps law of permutations?

Don't explain heap sort.

7/26/2020 7:05:26 AM


3 Answers

New Answer


There are N! permutations in all and generating all of them requires Θ(N!) time and Θ(N) space. In other words, each permutation requires amortised Θ(1) time. Those facts can be derived from the recursive algorithm presented on the Wikipedia page. In essence, the code alternates swaps and outputs so each output involves a single swap. However, there are also call operations and loop tests. There is a single loop test before each call, so it is only necessary to count the total number of calls. In the worst case, there will be n recursive calls before an output. But that only happens once, at the very beginning of the algorithm. A single call with argument n produces n! outputs. It does that with n recursive calls, each of which produces (n-1)! outputs, and does (n-1) recursive calls, so there are n(n-1) calls with argument n-2. And so on, so there are a total of 1 + n + n(n-1) + n(n-1)(n-2) + ... + n! calls. That can be written as Σ0≤i≤nn!/i! or (Σ0≤i≤n1/i!)n! Or (e-1), which is approximately 1.71828 n!


Jan Markus i couldn't get the last few lines


def generate(l,a): if l ==1 : print(*a) else: for i in range(l): generate(l-1,a) if i % 2==0: a[i],a[l-1] = a[l-1],a[i] else: a[0],a[l-1] = a[l-1],a[0] generate(3,[1,2,3]) Can you brak this down pls