  Holographic search algorithms such as direct search and simulated annealing
allow high-quality holograms to be generated at the expense of long execution
times. This is due to single iteration computational costs of $O(N_x N_y)$ and
number of required iterations of order $O(N_x N_y)$, where $N_x$ and $N_y$ are
the image dimensions. This gives a combined performance of order $O(N_x^2
N_y^2)$. In this paper we use a novel technique to reduce the iteration cost
down to $O(1)$ for phase-sensitive computer generated holograms giving a final
algorithmic performance of $O(N_x N_y)$. We do this by reformulating the
mean-squared error metric to allow it to be calculated from the diffraction
field rather than requiring a forward transform step. For a $1024\times 1024$
pixel test images this gave us a $\approx 50,000\times$ speed-up when compared
with traditional direct search with little additional complexity. When applied
to phase-modulating or amplitude-modulating devices the proposed algorithm
converges on a global minimum mean squared error in $O(N_x N_y)$ time. By
comparison, most extant algorithms do not guarantee a global minimum is
obtained and those that do have a computational complexity of at least $O(N_x^2
N_y^2)$ with the naive algorithm being $O((N_xN_y)!)$.
