© 2020 Society of Photo-Optical Instrumentation Engineers (SPIE). 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 (NxNy) and number of required iterations of order O (NxNy), where Nx and Ny 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 (NxNy). 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 (NxNy) 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 [ (NxNy) ! ].