Khuller; Matias Randomized Sieve ( Closest Pair Problem)
Jump to navigation
Jump to search
Time Complexity
$O(n)$
Space Complexity
$O(n)$, not sure if this is auxiliary not mentioned
(https://www.sciencedirect.com/science/article/pii/S0890540185710498, Theorem 2.3)
Description
Approximate?
Exact
Randomized?
Yes, Las Vegas
Model of Computation
not mentioned
Year
1995