CODEWITHSUNDEEP
algorithmsortingdata-structures
Layth Slewa
Layth Slewa

Reputation: 11

What sorting algorithm has Worst-Case time-complexity of O(n!)

I have looked all over the internet and cannot find such wc time-complexity sort algorithm.

And I believe it's not Bogo Sort since it's wc is not infinity

Upvotes: 1

Views: 771

Answers (1)

trincot
trincot

Reputation: 350477

Such an algorithm could be Heap's algorithm, enriched with a verification after each swap that checks whether the array is sorted. Each modification to the array made by Heap's algorithm takes amortised O(1) time, so it has an overall time complexity of O(n!).

Add to that the verification to see that the array is sorted. If we do that naively, this would take a time complexity of O(n) each time it runs, making the overall time complexity O(n!n).

But we could first count the number of consecutive inversions (which could be a value between 0 and n-1). This step has a time complexity of O(n). In light of the greater time complexity of Heap's algorithm, this is irrelevant.

Then we could see how each swap in Heap's algorithm influences that count. There can be up to 4 consecutive pairs that are influenced by a swap, so it takes constant time to verify how the count is modified by the swap. If after the swap the count is zero, we know the array is sorted.

In the worst case Heap's algorithm has to go through all permutations before the count is found to be zero, so that represents a worst case time complexity of O(n!)

Upvotes: 2

Related Questions