- Boundary elements are distributed uniformly.
- The number of unknowns is
*N*. - The number of boundary elements in a leaf is less than a fixed
number
*M*. - The summation in the infinite series (2.3),
(2.9), etc. is truncated at
*p*terms.

- Cost of Step 3:
In step 3 we compute multipole moments at leaves and translate
multipole moments.
- Computation of multipole moments
The number of leaves is
*N*/*M*, the number of boundary elements is*M*in a leaf and the number of the multipole moments to be computed in a leaf is*p*. Therefore the cost for computation of multipole moments is*O*(*pN*). - Translation of multipole moments
The number of M2M translations via (2.7) at level
is
and the cost per translation is
*O*(*p*^{2}). We iterate these translations from to . Therefore the cost for M2M translations is .

- Computation of multipole moments
The number of leaves is
- Cost of Step 4:
In step 4 we compute coefficients of the local expansion and
translate them.
- Computation of coefficients of the local expansion
The number of M2L translations via (2.10)
at level
is
and the cost per
translation is
*O*(*p*^{2}). We iterate these translations from to . Therefore the cost for M2L translations is . - Translation of coefficients of the local expansion
The number of L2L translations via (2.12)
at level
is
and the cost per
translation is
*O*(*p*^{2}). We iterate these translations from to . Therefore the cost for L2L translations is

- Computation of coefficients of the local expansion
The number of M2L translations via (2.10)
at level
is
and the cost per
translation is
- Cost of Step 5:
In step 5 we evaluate the contribution from adjacent cells at
all the leaves with direct computation and the contribution from
cells which are not adjacent with the local expansion at all the
leaves.
- Evaluation with direct computation
The number of leaves is
*N*/*M*and the cost for the direct computation per leaf is*O*(9*M*^{2}). Therefore the cost is*O*(9*MN*). - Evaluation with the local expansion
The number of leaves is
*N*/*M*and the number of boundary elements is*M*in a leaf. Also, we truncate the infinite series (2.9) taking*p*terms. Therefore the cost is*O*(*pN*).

- Evaluation with direct computation
The number of leaves is

From above estimation one can see that the computational cost for M2L translation is expensive. Therefore, M2L translation is the bottleneck in FMM. To make matters worse, the cost for M2L translation is