Range Medians
| dc.creator | Har-Peled, Sariel | |
| dc.creator | Muthukrishnan, S. | |
| dc.date | 2008-07-01 | |
| dc.date.accessioned | 2026-07-07T09:47:53Z | |
| dc.date.available | 2026-07-07T09:47:53Z | |
| dc.description | We study a generalization of the classical median finding problem to batched query case: given an array of unsorted $n$ items and $k$ (not necessarily disjoint) intervals in the array, the goal is to determine the median in {\em each} of the intervals in the array. We give an algorithm that uses $O(n\log n + k\log k \log n)$ comparisons and show a lower bound of $Ω(n\log k)$ comparisons for this problem. This is optimal for $k=O(n/\log n)$. | |
| dc.description | To appear in ESA 08 | |
| dc.identifier | https://arxiv.org/abs/0807.0222 | |
| dc.identifier | http://arxiv.org/abs/0807.0222 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/164008 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Other Computer Science | |
| dc.title | Range Medians | |
| dc.type | text |