## 3 Comparison among Different AC Signal Analysis Methods
### Processing Time
#### 3.1.1 Theoretical Algorithm Complexity  
In this section, we define the complexity of the algorithm according to two factors: \(N\) is the number of samples to be processed and \(N_{f}\) is the number of frequency components whose associated amplitudes and phases are desired. This complexity gives information about the expected asymptotic time response per number of samples and the double of the number of frequency components (Double, due to amplitude and phase, or real and imaginary part determination). All algorithms are described in Table 1. Theoretically, DTFT and Goertzel would have similar times as they both have the least complexity among the algorithms compared. Most of the computation consists of multiplication and accumulation, operating on the desired frequencies only, which makes them linear to both \(N\) and \(2N_{f}\). For a small number of frequencies \(N_{f}\), they may outperform FFT (Radix-2, or Radix-4, or Radix-8). However, from an approximate of \(N_{f}>log_{2}(N)\), FFT provides similar or lower computation times. In Figure 2a, the visualization of the better algorithm as a function of time complexity is shown. In this graph, the boundary line \(N_{f}>log_{2}(N)\) separates the two regions where Goertzel/DTFT are expected to have slightly lower complexity (red shades colors) and the regions where FFT has lower complexity (purple shades). Clear red and purple define ambiguous regions, in which one may out perform the other. Finally, DTFT and Goertzel's performances are not the same: While Goertzel uses a constant twiddle, requiring \(6N_{f}\) operation per iteration, DTFT requires the twiddle to be calculated for each point. Therefore, a coefficient lookup table for DTFT may be required to obtain \(6N_{f}\) operations per iteration, otherwise, \(14N_{f}\) operations per iteration are required. In addition, if \(2\pi\) is not set as a constant, or if time information, i.e., \(n\delta t\), is not calculated beforehand, an additional \(2N_{f}+2N_{f}\) operation for DTFT per iteration should be included. Cross-correlation is done by the multiplication and addition of the reference signal that is shifted in time to the input signals, requires for all the samples. It, therefore, has a complexity of \(O(2N^{2}N_{f})\). Next are the sine-fit methods. For linear least-squares sine-fit, the multiplication of \(A_{m}at\) to its conjugate has a time complexity of \(O((2N_{f})^{2}N)\). The inversion can be done using cofactor or adjoint matrix, one taking \(O((2N_{f}+1)! )\) while the other \(O((2 Nf)^{3})\), assuming adjoint method is used for inversion as it provides better performance for small \(N_{f}\), a complexity \(O((2 Nf)^{3})\) is required for matrix inversion. Last are two multiplications with respective complexity of \(O((2N_{f})^{2}N)\) and \(O(2N_{f}N)\). Therefore, the overall complexity could be estimated to \(O((2N_{f})^{2}N+(2N_{f})^{3}+2N_{f}N)\) \begin{table}
\begin{tabular}{c c c} \hline \hline
**Method** & **Type** & **Comp. Complexity** & **n. op/Iteration** \\ \hline FFT (Radix-2/4/8) & Transform & O(Nlog\({}_{2}\)N) & - \\ Goertzel & Filter & O(2N\(N_{f}\)) & 6 \(N_{f}\) \\ Cross-Correlation & Transform & O(2\(N_{f}\)N\({}^{2}\)) & - \\ Sine-fit (linear) & Transform & - \\ Sine-fit (non-linear) & Transform & - \\ DTFT & Filter/Transform & O(2\(NN_{f}\)) & 6\(N_{f}\) or 14 \(N_{f}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison between Computation Complexity of Several Methods of AC signal analysis per Number of Samples and Number of Frequency Components. Figure 2: (a) Time complexity of DTFT/Goertzel vs. FFT as a function of \(N\) and \(N_{f}\). (b) Time complexity of Sine-fit (linear) vs. FFT as a function of \(N\) and \(N_{f}\). Compared to FFT and shown in Figure 2b, the time complexity of linear least-squares sine-fit is less than FFT if there is only one frequency component. Otherwise, FFT has a slight advantage for \(N_{f}<100\), as indicated by light bluish-purple in the graph.