## 4 Experimental Analysis
### Parameter Settings
#### 4.3.3 Algorithmic Efficiency  
PPPCF mainly consists of three operations: local data processing, similarity calculation, and rating prediction. The local data processing operation can be further divided into two parts, one is the classification and encoding of ratings, the other is the differential privacy protection for ratings. As the local operation needs to traverse all the user-rating vectors in the dataset, its time complexity is \(O(n)\). Figure 4: _MAE_ of each algorithm with different privacy budgets \(\varepsilon\). (**a**) Movielens 1M; (**b**) Yahoo Music. Figure 5: _RMSE_ of each algorithm with different privacy budgets \(\varepsilon\). (**a**) Movielens 1M; (**b**) Yahoo Music. The item-item similarity calculation includes the similarity calculation of the sensitive rating pairs and the similarity calculation for the weakly sensitive rating pairs. Assuming that the number of sensitive rating pairs is \(k\), according to the execution process of BBBCF, when calculating the similarity of an item-item pair, it should traverse the weakly sensitive rating pairs once and the sensitive rating pairs iter times, so the time complexity is \(O(((k-1)\cdot iter+m)\), and the time complexity of the similarity calculation on the server side is \(O\big{(}((k-1)\cdot iter+m)\cdot n^{2}\big{)}\). From Equation (11), the time complexity of the user's local prediction for all items is \(O(n)\). Choose the DPLCF and LDP item-based CF algorithms, which also apply the localized differential privacy frameworks, for the comparative analysis. According to the calculation process of these two algorithms, the time complexity of their local data processing is also \(O(n)\), and the time complexity of the similarity calculation is \(O\big{(}m\cdot n^{2}\big{)}\). Additionally, since the rating prediction model used in the comparison algorithms is the same as PPPCF, so their time complexities of the rating prediction are \(O(n)\). Compared with all the comparison algorithms, the time complexity of the local data processing section and the rating prediction section of PPPCF is the same as others, but in the similarity calculation section, the time complexity of PPPCF is higher due to the need to iteratively reconstruct the distribution of rating data. However, since \(k\ll m\) and \(iter\ll m\), it is still in the same range as all the comparison algorithms. To further verify the results of the complexity analysis, taking the Movielens 1M and Yahoo Music datasets for example, assign \(\varepsilon\) and \(N\) be 1, 100, then evaluate the time overhead of each algorithm on the two datasets, experimental results are shown in Table 3. Each algorithm spends about the same amount of time on local data processing operations, with the PPCF algorithm having the least time overhead. This is because the PPPCF algorithm classifies the data sensitivity before perturbing the data, which greatly reduces the amount of data that needs to be perturbed. In the process of the similarity calculation, PPPCF is affected by \(k\) (i.e., number of the sensitive rating pairs) and iter (i.e., times of iterations), so multiple iterations are required to ensure a lower prediction error, causing its time overhead for the similarity calculation is greater than the other comparison algorithms. Meanwhile, the benefit of high time overhead is that its prediction error is lower than others. Additionally, PPPCF utilizes the Hamming distance to measure the similarity, and in the actual operation process, the Hamming distance between vectors can be obtained through XOR operation, which can improve the operation efficiency of PPPCF algorithm. This is confirmed by the fact that the Truncated PPPCE has a smaller time overhead in calculating similarity in Table 3. For the recommendation algorithm, the efficiency of the rating prediction calculation is particularly important, and the time taken to predict ratings for a single user on the Yahoo Music and Movielens 1M datasets is 6\(\sim\)7 ms and 78-81 ms, respectively, which can meet the actual needs.