Abstract | ||
---|---|---|
By developing and exploiting new in-place techniques, we show that finding the element with the median value out of n elements stored in an array can be performed in-place in (2.95+∈)n (for any ∈>0) comparisons and in linear time. This is arbitrarily close to the upper bound for the same problem without space-restrictions. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1007/BFb0015429 | ISAAC |
Keywords | Field | DocType |
linear-time in-place selection,linear time,upper bound | Discrete mathematics,Combinatorics,Computer science,Upper and lower bounds,Time complexity | Conference |
ISBN | Citations | PageRank |
3-540-60573-8 | 7 | 0.67 |
References | Authors | |
7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Svante Carlsson | 1 | 764 | 90.17 |
Mikael Sundström | 2 | 7 | 1.01 |