## 3 Robust Low-Complexity CFO Estimator
### Computational Complexity  
In this subsection, we investigate the computational complexity for [PERSON]'s and our proposed schemes, respectively, where the complexity is evaluated by counting the numbers of their required complex multiplications. For construction of the CFO-compensated data in Equation (5), it require \(2N^{2}+N\) complex multiplications. In addition, the calculation of \(\mathbf{J}\mathbf{F}_{K}^{H}\mathbf{D}_{\mathbf{X}_{p}}^{-1}\mathbf{S}\tilde{ \mathbf{R}}(\epsilon)\) and the vector norm needs \(K(K-\hat{L}-1)\) and \((K-\hat{L}-1)\) complex multiplications, respectively. As a result, the required complex multiplications for [PERSON]'s estimator using an \(N_{u}\)-section search are approximately expressed as:  
\[\text{CM}_{Chung}\approx N_{u}\left[N(2N+1)+(K-1)(K-\hat{L}-1)\right] \tag{39}\]  
As regards the proposed search-based scheme, the computation of the \((N-N_{g})\times N\) matrix \(\tilde{\mathbf{J}}\mathbf{F}^{H}\mathbf{Q}\mathbf{D}_{\mathbf{X}_{p}}\mathbf{ S}\mathbf{F}\), which is independent of the received data, can be pre-computed and saved in a lookup-table (LUT) ROM. Thus, the proposed search-based estimator only requires \(N(N-N_{g})\) complex multiplications for computing \(\tilde{\mathbf{J}}\mathbf{F}^{H}\mathbf{Q}\mathbf{D}_{\mathbf{X}_{p}}\mathbf{ S}\mathbf{F}\mathbf{D}_{\mathbf{r}}\). In addition, the calculation of CRE in Equation (14) needs \((N+1)(N-N_{g})\) complex multiplications for each of \(\epsilon\). Given an \(N_{u}\), the total number of complex multiplications for the proposed search-based estimator is approximately:  
\[\text{CM}_{Search-based}\approx(N-N_{g})\left[N(N_{u}+1)+N_{u}\right] \tag{40}\]  
To reach the \(j\)-th CFO estimate in Equation (37), the construction of the \(N\times N\) matrices \(\mathbf{\Phi}\) and \(\mathbf{\Psi}\) requires \(2N^{2}\) complex multiplications. In addition, we require \(N^{2}+N\) complex multiplications to compute either \(\mathbf{a}^{T}(\hat{\epsilon}_{d}^{j-1})\mathbf{\Phi}\mathbf{a}^{*}(\hat{ \epsilon}_{d}^{j-1})\) or \(\mathbf{a}^{T}(\hat{\epsilon}_{d}^{j-1})\mathbf{\Psi}\mathbf{a}^{*}(\hat{ \epsilon}_{d}^{j-1})\). Consequently, the total number of complex multiplications for the proposed iterative estimator is about:  
\[\text{CM}_{Iterative}\approx 2N\left[N(J+2)+J\right] \tag{41}\]  
Table 1 lists the computational complexity for the three CFO estimation approaches. Since \(N_{u}{\gg}1\), the proposed search-based estimation requires much lower computational complexity than [PERSON]'s scheme. Besides, inasmuch as \(J\ll N\), it is shown that the proposed iterative estimator significantly outperforms both [PERSON]'s and the proposed search-based schemes in computational complexity.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Algorithm** & **Numbers of Complexity Multiplications (CMs)** \\ \hline [PERSON]’s estimator in Equation (9) & \(N_{u}\left[N(2N+1)+(K-1)(K-\hat{L}-1)\right]\) \\  & \(\approx 2N_{u}N^{2},\ \ \ \ N\gg 1\) \\ \hline Proposed search-based estimator in Equation (16) & \((N-N_{g})\left[N(N_{u}+1)+N_{u}\right]\) \\  & \(\approx NN_{u}(N-N_{g}),\ \ \ \ N\gg 1\) \\ \hline Proposed iterative estimator in Equation (37) & \(2N\left[N(J+2)+J\right]\) \\  & \(\approx 2N^{2}(J+2),\ \ \ \ N\gg J\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison for the computational complexities among the proposed and conventional schemes.