39 citations · 87 across the 16 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
math.NT2007
Farey Statistics in Time n^{2/3} and Counting Primitive Lattice Points in Polygons
Mihai Patrascu
We present algorithms for computing ranks and order statistics in the Farey sequence, taking time O (n^{2/3}). This improves on the recent algorithms of Pawlewicz [European Symp. A…
cs.DS2007
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in…