Holographic search algorithms such as direct search (DS) 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_xN_y  )   and number of required iterations of order O  (  N_xN_y  )  , where N_x and N_y are the image dimensions. This gives a combined performance of order O(Nx2Ny2). We use a technique to reduce the iteration cost down to O  (  1  )   for phase-sensitive computer-generated holograms, giving a final algorithmic performance of O  (  N_xN_y  )  . We do this by reformulating the mean-squared error (MSE) metric to allow it to be calculated from the diffraction field rather than requiring a forward transform step. For a 1024  ×  1024-pixel test images, this gave us a ≈50,000  ×   speed-up when compared with traditional DS with little additional complexity. When applied to phase-modulating or amplitude-modulating devices, the proposed algorithm converges on a global minimum MSE in O  (  N_xN_y  )   time. By comparison, most extant algorithms do not guarantee that a global minimum is obtained. Those that do, have a computational complexity of at least O(Nx2Ny2) with the naive algorithm being O  [    (  N_xN_y  )    !    ]  .