# A Technique of Recursive Reliability-Based Missing Data Imputation for Collaborative Filtering
## 4 k-Recursive Reliability-Based Imputation (k-RRI)
### Comparison of Computational Complexity  
The purpose of this study is to enhance prediction accuracy; however, it is important to note that the dependence of computational complexity on the system size is also a significant factor. The benefit obtained by high prediction accuracy can be offset by a higher computational complexity, rendering the algorithm uncompetitive in a practical setting. Therefore, we conducted a theoretical comparison of EMDP, AutAI, and k-RRI with a focus on the computational complexity.  
Three imputation algorithms presented in this paper, namely EMDP, AutAI, and k-RRI, can generally be divided into the following process parts:  
* Key neighbor selection stage: selection of the key neighbors of interest.
* Missing data imputation stage [30]: identification of the missing data from the key neighbors and implementation of missing data imputation.  
Equations (13)-(15) represent the computational complexities of EMDP, AutAI, and k-RRI, respectively, where \(M\) and \(N\) denote the total numbers of users and items, respectively.  
\[\begin{array}{ll}time_{EMDP}&=time_{key\;neighbor\;selection}+time_{ missing\;data\;imputation}\\ &=O(MN)+O(\mathcal{N}_{EMDP})\\ &=O(MN+\mathcal{N}_{EMDP})\\ &=O(MN)\\ \end{array} \tag{13}\]  
\[\begin{array}{ll}time_{AutAI}&=time_{key\;neighbor\;selection}+time_{ missing\;data\;imputation}\\ &=O(MN)+O(\mathcal{N}_{AutAI})\\ &=O(MN+\mathcal{N}_{AutAI})\\ &=O(MN)\\ \end{array} \tag{14}\]  
\[\begin{array}{ll}time_{k-RRI}&=\left(time_{key\;neighbor\;selection}+time_{ missing\;data\;imputation}\right)\times k\\ &=\left(O\left(\frac{1}{2}M^{2}+\frac{1}{2}N^{2}+MN\right)+O(\mathcal{N}_{k- RRI})\right)\times k\\ &=O\left(k\left(\frac{1}{2}M^{2}+\frac{1}{2}N^{2}+MN\right)\right)+O(k \mathcal{N}_{k-RRI})\\ &=O\left(M^{2}+N^{2}+MN\right)+O(\mathcal{N}_{k-RRI})\\ &=O\left(max(M^{2},\;N^{2})\right)+O(\mathcal{N}_{k-RRI})\\ &=O\left(max(M^{2},\;N^{2})\right)+\mathcal{N}_{k-RRI})\\ &=O\left(max(M^{2},\;N^{2})\right)\\ \end{array} \tag{15}\]  
In the key neighbor selection stage, all elements of the user-item rating matrix should be identified, of which the computational complexity is \(O(MN)\). EMDP and AutAI implement this stage once, and k-RRI repeats it \(k\) times at each iteration, with the user-item rating data changing every time. Changes in the user-item rating data entail changes in the user and item similarities. Therefore, k-RRI updates the similarity matrix at every iteration. Here, the time required for updating the user similarity matrix is \(O\left(\frac{1}{2}M^{2}\right)\) and for the item similarity matrix is \(O\left(\frac{1}{2}N^{2}\right)\). The number of recursive steps \(k\) is a negligibly small constant irrespective of the numbers of users and items; thus, it can be disregarded in terms of big-O notation. Accordingly, the computational complexity of k-RRI in the key neighbor selection stage is \(O\left(k\left(\frac{1}{2}M^{2}+\frac{1}{2}N^{2}+MN\right)\right)=O\left(max(M ^{2},\ N^{2})\right)\).  
In the missing data imputation stage, all key neighbors are identified. Considering the characteristics of each algorithm, the numbers of key neighbors can be expressed by \(\mathcal{N}_{AutAI}\leq\ \mathcal{N}_{EMDP}\approx\mathcal{N}_{k-RRI}\ll MN\). That is, the computational complexity in the imputation stage is \(O(\mathcal{N}_{AutAI})\), \(O(\mathcal{N}_{EMDP})\), and \(O(\mathcal{N}_{k-RRI})\), with the maximum time requirement being \(O(MN)\). Given that the key neighbor selection stage is the dominant part in all three algorithms, the overall computational complexity is \(O(MN)\) for EMDP and AutAI, and \(O\left(max(M^{2},\ N^{2})\right)\) for k-RRI. For similar user and item data sizes, the overall computational complexity of all three algorithms is \(O(MN)\). This suggests that in a system with similar user and item data sizes, only prediction accuracy plays a role in algorithm selection.