## 6 Complexity Analysis  
In order to evaluate and compare the complexity of the different NLEs under test, we should first note that the nature of the deterministic equalizers based on DBP and IVSTF is essentially different from machine learning-based NLEs such as ANN and SVM. On the one hand, since DBP and IVSTF equalizers require an inversion of the propagation model, they are dependent on several link and bandwidth parameters. In particular, they depend on the number of spans of the oversampling parameter and, in the case of DBP, on the chosen spatial step. The complexity of these equalizers, though, does not depend a priori on other signal parameters such as modulation format. Machine learning based NLEs, on the contrary, present a complexity that does not depend on the link parameters but on some signal parameters, for instance the number of constellation points and the number of OFDM subcarriers. Hence, the computation of the complexity of each NLE family requires special attention. The following subsections deal with the complexity analysis of deterministic and machine learning approaches. In addition, we shall discuss the complexity of some clustering algorithms. For the sake of clarity in the derivation of the complexity expressions, the following table lists the employed parameters and their associated variable names (Table 2). We shall consider the number of operations to process an OFDM symbol. Hence, in order to obtain the number of operation-per-bit, the number of operations should be divided by the number of bits per OFDM symbol.  
Figure 12: Single-channel 16-QAM CO-OFDM [21; 28; 29; 30; 31; 33; 35; 36] results in terms of Q-factor vs. LOP for (**a**) clustering algorithms, (**b**) Fast-Newton-SVM (N-SVM), (**c**) unsupervised SVMs and (**d**) supervised SVM.  
Complexity Analysis of Digital Back-Propagation (DBP) and Inverse-Volterra Series-Transfer Function (IVSTF)-Based Non-Linear Equalizations (NLEs)  
Both DBP and IVSTF based NLEs can be implemented fully in the time domain, frequency domain, or in the hybrid time-frequency domain [13]. In this work, we assume the latter, as this is a commonly adopted approach in either DBP- or IVSTF-based NLEs. As indicated in previous section, in the case of DBP, the most widely employed method is the SSF with inverted parameter values. In this method, the CD is simulated in the frequency domain whereas the non-linear Kerr effect is simulated in the time domain. On the other hand, the IVSTF NLEs implemented in the hybrid time-frequency domain make use of the simpler calculation of high dimensional convolution in the frequency domain. Both methods, therefore, require multiple conversion from the frequency domain to the time domain and vice versa. This conversion is performed using FFT/IFFT pairs that operate on data blocks of size N\({}_{block}\) = \(K\cdot N_{signal}\), since the data has to be oversampled with an oversampling constant \(K\) in order to account for the out-of-band non-linear components. When the \(N_{block}\) is a power of two, the split-radix is the implementation showing the lowest complexity [13] requiring the floating-point (FLOPs) real-valued operations from (1):  
\[N_{FFT}=N_{IFFT}=4N_{block}\log_{2}N_{block}-6N_{block}+8 \tag{1}\]