3
$\begingroup$

In The Art of Computer Programming D. Knuth, in section 5.3.3 Minimum Comparison Selection defines :

  • $V_t(n)$ as the minimum number of comparisons needed to find the $t^{th}$ largest element of $n$ numbers
  • $W_t(n)$ as the minimum number of comparisons needed to find and sort the $t$ largest elements of $n$ numbers

Then, there is a table (Table 1.) that gives all values of $V_t(n)$ for $n\le 10$

My questions :

  1. Is there an updated table for known values of $V_t(n)$ somewhere ? (last results used by Knuth are from 1996).
  2. Is there a similar table for $W_t(n)$ ?
$\endgroup$
  • 1
    $\begingroup$ It might be a fun exercise if you try to write a program to compute that table. $\endgroup$ – Sagnik Oct 2 '18 at 11:58

Your Answer

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

Browse other questions tagged or ask your own question.