In this letter, a general auto-correlation based frequency offset estimation (FOE) algorithm is analyzed. An approximate closed-form expression for the Mean Square Error (MSE) of the FOE is obtained, and it is proved that, given training symbols of fixed length N, choosing the number of summations in the auto-correlation to be 〈N/3〉 and the correlation distance to be 〈2N/3〉 is optimal in that it minimizes the MSE. Simulation results are provided to validate the analysis and optimization.