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.