For the second largest element, I know that the formula is $n+ \lceil\log n \rceil -2 $

Is there any formula for the third largest element? and if so, what is the derivation?

  • $\begingroup$ For rank $k$ you must perform at least $n-k+\log \binom{n}{k-1}$ $\endgroup$ – lox Jul 5 '19 at 7:14
  • $\begingroup$ is k-1 the base of log or the combination like nC(k-1) ? $\endgroup$ – CS_GUY Jul 5 '19 at 7:24
  • $\begingroup$ n over k is a common notation and means binomial expansion of the k-th power in polynomial of order n $\endgroup$ – lox Jul 5 '19 at 8:27

For the problem of computing the $k$-th rank element, a lower bound of $n-k+\log \binom{n}{k-1}$ can be proven with decision trees.

For simplicity this proof assumes that the element set $X$ is of size $n$ and its elements are distinct (which makes the problem harder). Moreover, the algorithm may only compare any two elements, and conclude one is either smaller or greater than the other.

First, let us claim the following:

For computing the $k$-th rank element (denoted $x_k$) (using comparisons only), every other element $x_i$ must be involved in a comparison that sets it lesser or greater than the $k$-th rank element.

Formally: for any $x_i$ lesser than $x_k$, $x_i$ must be involved in a comparison of the sort $x_i < x_j \leq x_k$. For any $x_i$ greater than $x_k$, it must be involved in the comparison $x_i > x_j \geq x_k$

The proof by contradiction: Suppose $x$ was not involved in either those comparisons. Then $x$ can be either greater or smaller than $x_k$, which means the $k$-th rank element can change depending on $x$.

Let $\mathcal{T}$ be a decision tree that finds the $k$-th rank element. We will show $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves.

Now, suppose $T_1$ is another decision tree, that knows the set of elements greater than $x_k$, denoted by $K_1$. It means $T_1$ does not need to compare any elements of $K_1$, and thus performs $n-k$ comparisons, or has $2^{n-k}$ leaves.

Because of the claim we made earlier, we know $\mathcal{T}$ must have performed the comparisons in $T_1$, hence for each leaf in $T_1$ there is a corresponding leaf in $\mathcal{T}$. Moreover, in each of these leaves, the element $x_k$ defines the set $K_1$, which are all the elements greater than $x_k$.

How many trees like $T_1$ are there? As many as the different choices you can make for the set $K_1$, which is selecting $k-1$ elements out of $n$, which is exactly $\binom{n}{k-1}$. And for each of these trees, there are at least $2^{n-k}$ leaves in $\mathcal{T}$, which are essentially distinct, since they define distinct sets $K_i$.

It follows that $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves, therefore the lower bound is $\log$ of the same:

$$n-k+\log \binom{n}{k-1}$$

| cite | improve this answer | |

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.