- #1
morasas
- 2
- 0
Show how to find the t-th largest element (t - 1 elements are larger and
n - t elements are smaller) in the set of n elements in (n - t) + (t - 1)log (n - t + 2) comparisons.
I'v etried as hard as I can to solve this, and I came to relalize that i need to divide the array into two groups, one of (n-t+1) and the other to (t-1) elements.
i can find the largest element in the (n-t+1) group, which will be the t-th largest element of all.
what i can't understand is what should i do with the log expression. what is the +2 element inside the brackets stands for...
will appreciate an answer, thanks.
n - t elements are smaller) in the set of n elements in (n - t) + (t - 1)log (n - t + 2) comparisons.
I'v etried as hard as I can to solve this, and I came to relalize that i need to divide the array into two groups, one of (n-t+1) and the other to (t-1) elements.
i can find the largest element in the (n-t+1) group, which will be the t-th largest element of all.
what i can't understand is what should i do with the log expression. what is the +2 element inside the brackets stands for...
will appreciate an answer, thanks.