Re: problem on medians
- From: Mark F <mark49607@xxxxxxxxx>
- Date: Thu, 31 May 2007 08:19:50 -0400
On 31 May 2007 00:49:50 -0700, ak <ajinkya.coep@xxxxxxxxx> wrote:
what are the least no. of comparisons to find the medain of a set ofThis says it is O(n), where "n" is the number of elements:
n integers ?
http://en.wikipedia.org/wiki/Median#Efficient_computation
http://doi.acm.org/10.1145/22145.22169
says it requires at least 2*n comparisons.
(In case you don't have access to the ACM Portal, here is the
reference:
"Proceedings of the seventeenth annual ACM symposium on Theory of
Computing", Providence, Rhode Island, United States
"Finding the median requires 2n comparisons",
Samuel W. Bent and John W. John {yes, first and last names the same}
Pages: 213 - 216 Year of Publication: 1985 ISBN:0-89791-151-2
Using Google for:
comparisons "finding the median"
gives many other references. I saw a reference giving 10*n as a
worst case performance. There is also a "random" algorithm with
good average performance but n*n worst case performance.
.
A K
- References:
- problem on medians
- From: ak
- problem on medians
- Prev by Date: Re: problem on medians
- Next by Date: Re: divide & conquer algorithm to implement string matching
- Previous by thread: Re: problem on medians
- Next by thread: Re: problem on medians
- Index(es):
Relevant Pages
|
