| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428111 | Information Processing Letters | 2009 | 4 Pages |
Abstract
Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n2/logn) to O(n2loglogn/log2n) words.For median the space bound is improved to O(n2loglog2n/log2n) words from O(n2⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
