patternMinor
(Nontrivial) Algorithms for finding the third largest element of a set
Viewed 0 times
nontrivialthethirdalgorithmslargestforelementfindingset
Problem
According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for finding the third largest in a set of $n$ distinct elements?
Given that the tight lower bound is still unknown, I want to know the algorithms currently published in papers (meaning that they are not trivial, for example, by finding and removing the largest and the second largest elements and finding the third largest one in $(n-1) + (n-2) + (n-3) = 3n - 6$ time) for finding the third largest element.
Searching for "algorithm finding the third largest element" in Google does not bring me useful references.
Given that the tight lower bound is still unknown, I want to know the algorithms currently published in papers (meaning that they are not trivial, for example, by finding and removing the largest and the second largest elements and finding the third largest one in $(n-1) + (n-2) + (n-3) = 3n - 6$ time) for finding the third largest element.
Searching for "algorithm finding the third largest element" in Google does not bring me useful references.
Solution
For $n>5$, this paper proves that the number of comparisons
deterministic algorithms need is $n + \big(2 \cdot \lfloor \log_{2}(n)\rfloor \big) - \big(\text{an element of } \{1,2,3\}\big)$,
where that element depends on $n$'s position relative to the nearby powers of $2$.
Furthermore, for $n>7$, that paper gives a
deterministic algorithm which achieves those values.
By pages 330 and 331, the average number of comparisons needed is $n + \Theta(\ln\ln n)$.
Theorem 5 is that the average number of comparisons used by that
paper's algorithm is at most $n + 5 \cdot ( 11 + \ln\ln n)$.
I have currently not located anything else regarding non-worst-case
algorithms for your problem, although I've kept finding more as I go along.
deterministic algorithms need is $n + \big(2 \cdot \lfloor \log_{2}(n)\rfloor \big) - \big(\text{an element of } \{1,2,3\}\big)$,
where that element depends on $n$'s position relative to the nearby powers of $2$.
Furthermore, for $n>7$, that paper gives a
deterministic algorithm which achieves those values.
By pages 330 and 331, the average number of comparisons needed is $n + \Theta(\ln\ln n)$.
Theorem 5 is that the average number of comparisons used by that
paper's algorithm is at most $n + 5 \cdot ( 11 + \ln\ln n)$.
I have currently not located anything else regarding non-worst-case
algorithms for your problem, although I've kept finding more as I go along.
Context
StackExchange Computer Science Q#72503, answer score: 7
Revisions (0)
No revisions yet.