2
$\begingroup$

Let says you want to k-sort an array A with a comparison based algorithm. To be k-sorted, each individual item in the array A can be at most k positions away from it's actual correct position when fully ordered. I was trying to come up with a decision tree argument for why this algorithm must be at least Ω(nlog n), but I can't find a bounds for the numbers of leaves in the tree that make this work. At first I was thinking that maybe there has to be at least n!/(2k+1)^n leaves in the tree, but I don't think that is correct.

Anyone know how to make a decision tree argument for this? To be clear - the algorithm is performing the k-sorting of the array A, it is NOT receiving a k-sorted array.

$\endgroup$

1 Answer 1

1
$\begingroup$

I'll assume that the arrays do not have any repeated numbers, so we can treat the input and output arrays as a permutation of $1,2,\dots,n$.

For each output permutation, there are at most $(2k+1)^n$ input permutations that are consistent with it (i.e., such that the output permutation is a $k$-sorted version of the input). So if your decision tree has $L$ leaves, then the algorithm will have at most $L$ possible output permutations, and then there are at most $L (2k+1)^n$ possible inputs that could be consistent with these possible outputs.

There are $n!$ input permutations. It follows that we must have $L (2k+1)^n \ge n!$ in any correct decision tree. (If $L(2k+1)^n < n!$, then there must exist some input permutation that is not consistent with any of the output permutations that can be produced by the decision tree, i.e., there must exist some input permutation that is not correctly $k$-sorted by the algorithm.) Re-arranging, we find that we must have

$$L \ge n!/(2k+1)^n.$$

So your belief was indeed correct.

The depth of the tree must be at least $\lg L$. From the above, it follows that the tree must have depth at least $\lg (n!/(2k+1)^n)$. If you expand that out, I think you'll find that it implies your desired lower bound on running time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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