Aluru, Srinivas (1993) Greengard's N-body Algorithm is not order N. Technical Report TR93-29, Department of Computer Science, Iowa State University.
Greengard's N-Body Algorithm is Not Order N
Ames Laboratory, Iowa State University, Ames, IA 50011.
Greengard's N-body algorithm claims to compute the pairwise interactions in a
system of N particles in O(N) time for a fixed precision. In this paper,
we show that the choice of precision is not independent of N and has a
lower bound of log N. We use this result to show that Greengard's algorithm
is not O(N).
Contact site administrator at: email@example.com