The backprojection (i.e. Step 2 in Algorithms 1-3) is the most time consuming part of the filtered backprojection algorithm. The filtering or convolution step (Step 1 in Algorithms 1-3) requires in principle the same number of operations, but this can easily be reduced drastically either by cutting off the filter or by using the fast Fourier transform (FFT).

The backprojection consists is the evaluation of the sums

on a grid. This is the simplest case of Algorithm 1, the resolution of the image being adjusted to the number of views *p* according to the sampling theorem. Nilsson
(1997) suggested a devide and conquer strategy for doing this with O operations, as opposed to the O operations of a direct evaluation. Suppose .

**Step 1:** For compute

Since is constant along the lines it suffices to compute at *2p* points *x*. We need operations.

**Step 2:** For compute

Since , are constant along the lines , , respectively, is almost constant along the lines where .
Hence it suffices to compute only for a few, say 2, points on each of those lines.
This means that we have to evaluate at *4p* points, requiring operations.

**Step 3:** For compute

With the same reasoning as in step 1 and 2 we find that it suffices to compute for only for *8p* points, requiring operations.

Proceeding in this fashion we arrive in step *m* at the approximation to *f*,
which has to be evaluated at points. Hence the number of operations in step 1 to *m*
is

and this is O . Of course this derivation is heuristic, and we simply ignored the necessary interpolations and approximations. But practical experience demonstrates that such an algorithm can be made work.

Thu Sep 10 10:51:17 MET DST 1998