Publication Date

12-30-1993

Technical Report Number

TR93-29

Subjects

Mathematics of Computing

Abstract

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).

Share

COinS