5
$\begingroup$

Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).

My proof is a simple modification of the decision tree argument used to obtain the lower bound for comparison-based sorting of one array. More specifically, I argue that there are in total $k!^n$ possible permutations for the entries in all given arrays, and that a binary tree with that number of leaves is of height $h \in \Omega(nk \log k)$. Is that argument correct?

Furthermore, I was told that merely observing that one needs $\Omega(k \log k)$ comparisons for each of the arrays and we need to sort $n$ times in total (for $n$ arrays) is not a sufficient argument. Why is that? My answer would be that this is just one possible approach to this problem, and not a general argument excluding each and every other potential comparison-based algorithm for solving the given task with less than $\Omega(nk \log k)$ comparisons. However, this is not particularly concise and I would consider a rather technical argument (which I don't see) as more appropriate. What would that be?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ actually you have $k!^n$ possible permutations $\endgroup$ – ratchet freak Mar 29 '13 at 12:54
  • $\begingroup$ Yes, this is what was meant (as follows from the otherwise incorrect height bound given later in the text). Thank you. $\endgroup$ – Cornelius Brand Mar 29 '13 at 13:27
6
$\begingroup$

For the first part, as the comments suggest - observe that there are $k!^n$ possible permutations for the inputs - indeed, every array has $k!$ permutations, and there are $n$ arrays, so you have $k!$ options for the first array, $k!$ for the second, and so on.

So the height of a decision tree is $$\log (k!^n)=n\log (k!)\in \theta(nk\log k)$$ So you need at least that many comparisons in order to determine a single leaf.

For the second part - the argument you suggest is quite close to a formal explanation. The lower bound of $\Omega(k\log k)$ is for comparison-based algorithms that compare elements in the array. When you have several arrays, then it is not justified to assume that sorting them is equivalent to sorting each one independently.

A-priori, it may be easier to sort them by comparing elements between the arrays. But the lower bound on sorting does not utilize such a setting, so it is not directly relevant for this problem.

In my opinion, this is as formal as you can get without formally defining what a comparison-based algorithm actually is. To define the latter, you need to formally model the computational model you use (which would be a sort of pointer-machine), and this is unlikely to result in any insights other than what you already mentioned.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why do you get $\Theta$ instead of $\Omega $ ? Task was about $\Omega$. $\endgroup$ – user40545 Nov 7 '15 at 22:04
  • 1
    $\begingroup$ We can get $\Theta$, so why not... It implies $\Omega$ by definition. But indeed, we could have just written $\Omega$. $\endgroup$ – Shaull Nov 7 '15 at 22:28
  • $\begingroup$ Ok, I thought so :D $\endgroup$ – user40545 Nov 7 '15 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.