Planar FMM operation count under explicit linear-size tree and list bounds

At each nonempty leaf, P2M accumulates $p+1$ moments per resident source, so the total is at most $N(p+1)$ operations up to a constant. The nonempty cells form a rooted connected subtree, so enumerating them by inspecting four children per nonempty internal cell costs $O(T)$ and yields exactly $T-1$ parent-child edges whose two cells are nonempty. On each such edge, M2M or L2L evaluates triangular sums with ${\sum }_{n=0}^p(n+1)=(p+1)(p+2)\mathrm{/}2$ terms, hence at most $O((p+1{)}^2)$ operations. Empty-child moments are zero and their edges are skipped. Initializing the local vectors costs $O(T(p+1))$, and both this and the $O(T)$ enumeration cost are absorbed in the displayed bound.

For each of the $K$ far pairs, M2L forms $p+1$ coefficients, each using at most $p+1$ terms, and evaluates the fixed logarithm once at the pair center; this costs $O(K(p+1{)}^2)$ because $p\ge 1$. L2P evaluates one degree-$p$ polynomial and its derivative at each of $N$ targets in $O(N(p+1))$ operations.

The recursive list decomposition uses $V$ cell-pair inspections. Each of the $J$ direct near particle-pair evaluations uses a constant number of arithmetic operations and one fixed-logarithm evaluation. By [F3] no required pair is counted twice or omitted; the work to dispatch the finite lists is included in these counts.

Adding the counts from steps 1.1, 1.2, and 1.3 gives the displayed operation bound after increasing one absolute constant $C_0$. The assumptions $T,V\le CN$, $K\le CT$, and $J\le CN$ then give $O(N(p+1{)}^2)$; since $p\ge 1$, $(p+1{)}^2\le 4p^2$, giving $O(N{p}^2)$. No bound on the cost of constructing the input quadtree or assigning its points was used.