Fast and accurate frequency estimation of a complex sinusoidal plays an important role in many applications, including communications, radar, and sonar. This paper presents two methods for the frequency estimation of a complex sinusoidal in noisy environments. The proposed methods interpolate on shifted DFT coefficients to acquire the frequency estimates iteratively. The first method interpolates on the q-shifted DFT coefficients of the signal, whose optimum iteration number is found to be a logarithmic function of the signal length. Furthermore, we also show that by appropriately selecting the value of the shift q, the proposed method becomes asymptotically efficient. In the second method, we use hybrid half-shifted and q-shifted DFT interpolators together, which converges in only two iterations. It is shown that both of the estimators are asymptotically unbiased with their mean square errors performing on the Cramer-Rao lower bound. Theoretical results are validated by extensive computer simulations.