# Symbol-Level Selective Channel Estimation in Packet-Based OFDM Systems
## 5 Complexity Analysis  
In this section, a complexity analysis of the proposed SLS scheme is performed for comparison with other channel estimation schemes such as TRFI and DD-TT. We employed an analytical method using the standard Landau notation, which is widely used to calculate the efficiency of an algorithm [19]. The Landau notation provides a high level of complexity without having to drill down into the detail of counting floating-point operations per second or individual operations.  
Because the SLS scheme is sequentially conducted on a symbol-by-symbol basis in the packet, the complexity analysis on one OFDM symbol can be extended linearly to calculate the complexity of the entire packet. Assuming that the total number of subcarriers to be estimated in one OFDM is \(N\), the complexity of each step of the SLS scheme can be simplified as shown in Table 3. Table 3 shows the complexity for the corresponding steps in the flowchart of Figure 2.  
The SLS scheme basically consists of Steps 1\(\sim\)4 to select a better scheme. The SLS scheme performs 1D cubic spline interpolation on the number of indexes \(R\) belonging to \(\mathcal{K}_{S}\) to obtain \(H_{CSI}(m,k)\). The 1D cubic spline interpolation with \(R\) points has the complexity \(O(R+\log R)\)[29]. In addition, time truncation using an FFT matrix is performed to obtain the channel estimate \(H_{TT}(m,k)\) of the DD-TT. The FFT matrix size is scaled as \(N\times L\), where \(L\) represents the channel order. The channel  
\begin{table}
\begin{tabular}{l c} \hline \hline
**Steps** & **Time Complexity** \\ \hline
1 & Initial Channel Estimation & \(O(2\cdot N)\) \\
2 & 1D Cubic Spline Interpolation & \(O(R+\log R)\) \\
3 & Time Truncation & \(O(2\cdot L\cdot N)\) \\
4 & Correlation Coefficient & \(2\cdot O(N)\) \\
6 & Time Reliability Test & \(O(2\cdot N)\) \\
7 & 1D Cubic Spline Interpolation & \(O(P+\log P)\) \\ \hline Overall Steps & \(O(N)\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Time complexity of steps for the SLS scheme.  
Figure 3: Mean correlation coefficient according to SNR.  
estimate \(H_{TT}(m,k)\) is obtained by the multiplication of the FFT matrix and the initial channel estimate vector; thus, the step of performing DD-TT has a complexity of \(O(2\cdot L\cdot N)\). If TRFI is selected, then Steps 6 and 7 are performed additionally. In 7, \(P\) is the number of initial channel estimates that have not passed the time reliability test, and it is determined by a number from 0 to 48 depending on the test result.  
Overall, the SLS scheme has a linear time complexity \(O(N)\) in one OFDM symbol. In the IEEE 802.11p standard, because \(N\) is a fixed value, the complexity of the SLS scheme depends on the \(M\) OFDM symbols that comprise one packet, i.e., the SLS scheme has the time complexity \(O(M)\).  
TRFI and DD-TT perform Steps 1, 6, and 7, and Steps 1 and 3, respectively, as shown in Table 4. Based on the analysis of the step-by-step complexity in Table 3, TRFI and DD-TT also have a linear time complexity \(O(N)\) in one OFDM symbol, and are affected by the number of OFDM symbols in the packet.  
Consequently, the SLS scheme has a linear time complexity like the DD-TT and TRFI schemes. However, in more detail, as SLS performs additional steps compared with TRFI and DD-TT, the computational speed is TRFI \(<\) DD-TT \(<\) SLS.