Inter carrier interference and multiple access interference are induced in uplink OFDMA systems due to Carrier Frequency Offset (CFO) which is a mismatch between the transmitter and receiver frequencies that in turn affects the orthogonality among subcarriers. A different CFO value is experienced by each user data and each of these CFO values needs to be estimated and corrected. A novel Extended Viterbi-and-Viterbi (EVAV) algorithm is employed for CFO estimation in the present study. A conventional algorithm for CFO compensation that deals with Minimum Mean Square Error (MMSE) filter output, involves inversion of interference matrix, adding to the computational complexity. The complexity was found to increase with the number of subcarriers. Hence, here an iterative Conjugate Gradient (CG) method is used to compute the MMSE filter output without an inverse operation, thereby reducing the complexity. Both the EVAV method and the CG method have been analyzed in terms of various performance measures. The results showed that they function better than their conventional counterparts. © 2014 IEEE.