CODEWITHSUNDEEP
algorithmsortingselectioncomplexity-theoryquicksort
glerYbo
glerYbo

Reputation: 1

Proof of Ω(n logk) worst case complexity in a comparison sort algorithm

I'm writing a comparison algorithm that takes n numbers and a number k as input.

It separates the n numbers to k groups so that all numbers in group 1 are smaller than all numbers of group 2 , ... , smaller than group k.

The numbers of the same group are not necessarily sorted.

I'm using a selection(A[],left,right,k) to find the k'th element , which in my case is the n/k element (to divide the whole array in to 2 pieces) and then repeat for each piece , until the initial array is divided to k parts of n/k numbers each.

It has a complexity of Θ(n logk) as its a tree of logk levels (depth) that cost maximum cn calculations each level. This is linear time as logk is considered a constant.

I am asked to prove that all comparison algorithms that sort an Array[n] to k groups in this way, cost Ω(nlogk) in the worst case.

I've searched around here , google and my algorithm's book (Jon Kleinberg Eva Tardos) I only find proof for comparison algorithms that sort ALL the elements. The proof of such algorithm complexity is not accepted in my case because all of these are under circumstances that do not meet my problem, nor can they be altered to meet my problem. ( also consider that regular quicksort with random selection results in Θ(nlogn) which is not linear as Ω(nlogk) is)

You can find the general algorithm proof here: https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf where it is also clearly explained why my problem does not belong in the comparison sort case of O(nlogn)

Upvotes: 0

Views: 2296

Answers (2)

rcgldr
rcgldr

Reputation: 28818

prove that all comparison algorithms that sort an Array[n] to k groups in this way, cost Ω(nlogk) in the worst case.

I think the statement is false. If using quickselect with a poor pivot choice (such as always using first or last element), then the worst case is probably O(n^2).

Only some comparison algorithms will have a worst case of O(n log(k)). Using median of medians (the n/5 version) for the pivot prevents quickselect solves the pivot issue. There are other algorithms that would also be O(n log(k)).

Upvotes: -1

David Eisenstat
David Eisenstat

Reputation: 65427

Sorting requires lg(n!) = Omega(n log n) comparisons because there are n! different output permutations.

For this problem there are

   n!
-------
      k
(n/k)!

equivalence classes of output permutations because the order within k independent groups of n/k elements does not matter. We compute

      n!
lg ------- = lg (n!) - k lg((n/k)!)
         k
   (n/k)!

           = n lg n - n - k ((n/k) lg (n/k) - n/k) ± O(lg n + k lg (n/k))
             (write lg (...!) as a sum, bound with two integrals;
              see https://en.wikipedia.org/wiki/Stirling's_approximation)

           = n (lg n - lg (n/k)) ± O(lg n + k lg (n/k))

           = n lg k ± O(lg n + k lg (n/k))

           = Omega(n lg k).
             (O(lg n + k lg (n/k)) = O(n), since k <= n)

Upvotes: 3

Related Questions