## 4 Computational Complexities  
The use of pilot symbols in coherent optical communication systems has been investigated for cycle slip analysis [42; 43], as a way to avoid differential coding. Cycle slips are particularly common in long-range communication systems. As discussed in the Introduction, the overhead for pilot symbols is set at 3% of the total transmitted symbols, resulting in an SNR penalty of 0.13 dB. This penalty is calculated using the formula \(\frac{P}{P+D}\), where \(P\) represents the length of the pilot sequence and \(D\) represents the length of the transmitted data. These studies highlight that the main drawback of using pilot symbols is the reduction in spectral efficiency, which is why an overhead of up to 5% is recommended. The BPS algorithm is widely recognized as a benchmark for carrier recovery processing. However, its computational complexity is significantly affected by the relationship between the number of test phases and the modulation order. Specifically, the number of test phases scales as \(2^{4}\), \(2^{5}\), and \(2^{6}\) for 16 QAM, 64 QAM, and 256 QAM, respectively, leading to high computational demands. Various studies have focused on improving the efficiency of BPS implementation, often combining techniques in two stages, as demonstrated in [44]. Furthermore, the use of differential coding in BPS presents additional challenges, which has led recent research to explore alternative approaches. One promising solution is the use of recursive probability weighting based on phase variance levels, which can reduce the number of test phases required [45]. The BPS algorithm works by testing a set of discrete phase values across the received signal block and selecting the phase that minimizes a cost function, typically related to the  
Figure 17: Residual phase noise, 64 QAM modulation, linewidth as \(\Delta\
u=$800\,\mathrm{kHz}$\times 2\), \(\mathrm{SNR}=$25\,\mathrm{dB}$\), (**a**) residual noise difference, (**b**) quantile–quantile of the residual phase noise. magnitude of the error vector. The computational complexity of BPS is driven primarily by the phase testing stage, resulting in a complexity of \(\mathcal{O}(NB)\). This means that complexity scales linearly with the number of test phases, \(B\), and the size of the processed symbols, \(N\), which makes BPS computationally expensive compared to other phase estimation methods, where the selection of \(N\) and \(B\) can significantly influence both the performance of the algorithm and its computational burden. For the Cosine-RLOWESS interpolation method, the first step involves extracting the pilot symbols and phase information from the input signal. This process results in a computational complexity of \(\mathcal{O}(N)\), where \(N\) represents the total number of symbols, indicating that the algorithm has a linear computational complexity. The LOWESS method involves locally weighted regression over a sliding window that moves across the data points. The computational complexity of this method depends on the number of operations performed for each data point within its local window. Generally, the complexity is \(\mathcal{O}(nm)\), where \(n\) represents the number of points to smooth and \(m\) denotes the span or window size, which corresponds to the number of points used in each local regression. Typically, \(m\) is much smaller than \(n\), and its effect is most significant when it constitutes a substantial fraction of \(n\). In this context, \(n\) refers to the pilot spacing and \(m\) is set to \(5\%\) of that length. If \(m\) is considered constant for practical purposes or is restricted to a small fraction of \(n\), the complexity can be approximated as \(\mathcal{O}(n)\). Since the LOWESS method is applied to the entire set of \(N\) symbols, the overall computational complexity of the algorithm becomes \(\mathcal{O}(N)\times\mathcal{O}(mn)=\mathcal{O}(Nmn)\).