Parameter estimation of multiple sinusoids is one of the fundamental problems of signal processing having numerous application areas, including wireless communications and array signal processing. This article proposes an iterative, fast, and efficient algorithm to estimate the frequencies and amplitudes of multiple sinusoids in noisy environments. The proposed approach interpolates on the q-shifted DFT coefficients of multiple sinusoids. We theoretically demonstrate that the performance of the proposed algorithm depends on DFT-shift, number of iterations and minimum DFT frequency separation parameters. Further, mean square error of the proposed algorithm achieves the Cramer-Rao lower bound when these parameters are selected appropriately. We also propose solid bounds regarding how these parameters can be selected for optimum overall performance. The total computational cost of the proposed algorithm is in the order of O( KN logN), where K is the number of sinusoidal components and N is the signal length. We provide comprehensive numerical simulations that confirm the correctness of our theoretical deductions.