# Real-Time Anomaly Detection with Subspace Periodic Clustering Approach
## 5 Complexity Analysis  
For generating dominance classes and corresponding classes, the algorithm needs to compare the values of all the possible pairs of objects from \(U\) in all dimensions, there can be at most \(\mid U\mid\times\mid U\mid\times\mid C\mid\) number of comparisons. So, the computational complexity for step1 is \(\text{O}(n^{2}.d)\), where \(\mid U\mid=n\), and \(\mid C\mid=d\). For generating the nano topology,  
Figure 4: Flowchart of the proposed method (RADSPCA). the lower approximation and approximation of the set has to be generated, which takes computational time \(\mathrm{O}(\left\lfloor\,X\,\right\rfloor.\left\,\left\lvert\,U\,\right\rvert)\). So the total computational cost of step1 and step2 is \(\mathrm{O}(n^{2}.d+\left\lvert\,X\,\right\rvert.\left\,\left\lvert\,U\,\right\rvert \right\rvert)=\mathrm{O}(n^{2}.d)\) which is the worst-case complexity. From step3 for loop starts it runs over at most all the attributes of the attribute set. The computation from step 4 to step7 takes constant time, say \(\mathrm{O}(k_{1})\), where \(k_{1}=\mathrm{constant}\). Therefore, the computational cost from step3 to step8 is \(\mathrm{O}(k_{1}d)\). Similarly, that of step9 and 10 is also constant, say \(\mathrm{O}(k_{2})\), where \(k_{2}=\mathrm{constant}\). The overall complexity of algorithm1 is \(\mathrm{O}(n^{2}.d+k_{1}d+k_{2})=\mathrm{O}(n^{2}.d)\). For finding the complexity of Algorithm2, the following steps are taken. Let \(k(\leq n)\) be the number of clusters. The computational cost of a centroid is \(\mathrm{O}(n+n.k.d_{1})=\mathrm{O}(n.k.d_{1})\), where \(d_{1}\) (\(\leq\)\(d\)), is the dimension of the CORE. Also, \(\mathrm{O}(2n.k)=\mathrm{O}(n.k)\) is the time required compute the minimum distance and time-gap for each cluster. The cost of updating cluster-mean and lifespan is \(\mathrm{O}(2k)\). The total cost of algorithm2 is \(\mathrm{O}(\mathrm{i}(n.k.d_{1}+n.k+k))=\mathrm{O}(i.n.k.d_{1})=\mathrm{O}(n ^{3})\) as \(i(\leq n)\), the number of iterations, \(k\leq n\), and \(d_{1}\) is considerably small. The worst-case complexity of the whole method is \(\mathrm{O}(n^{2}.d+n^{3})\). For finding the time-complexity of Algorithm 3, we proceed as follows. Let \(n_{1}\) be the size of the sequence of time intervals associated with a cluster and \(n_{2}\) be the average number of time intervals superimposed. For each time interval of a cluster, it is required to make a pass through the list of superimposed time intervals to check whether the corresponding time interval can be superimposed on any of the available superimposed time intervals or not. For this, the intersection of the current time-interval with the core of the superimposed time interval is computed, which requires \(\mathrm{O}(1)\) time. If the current time interval is superimposed, then its boundaries have to be inserted into two sorted arrays used to keep the end points of the superimposed time-intervals (one sorted array for left end points and other for right end points). Now, searching in a sorted array requires \(\mathrm{O}(\log\,n_{1})\) time and insertion needs \(\mathrm{O}(n_{1})\) time. The two end points require \(\mathrm{O}(2(\log\,n_{1}+n_{1}))=\mathrm{O}(n_{1})\) time. For one cluster, the process requires \(\mathrm{O}(n_{1}.p.n_{2})\) time, where \(p\) is the size of the list of superimposed time intervals. On the other hand, \(p=\mathrm{O}(n_{1})\), and \(n_{2}=\mathrm{O}(n_{1})\); the overall time-complexity in the worst-case is \(\mathrm{O}(n_{1}^{3})\). For \(k\) clusters, the total time-complexity in worst-case is \(\mathrm{O}(k.n_{1}^{3})\). Therefore, the worst-case complexity of the whole method is \(\mathrm{O}((n^{2}.d+n^{3})+k.n_{1}^{3})\). Also \(k=\mathrm{O}(n)\), which gives the time-complexity, as \(\mathrm{O}(n^{2}.d+n^{3}+n.n_{1}^{3})=\mathrm{O}(n^{3}+n.n_{1}^{3})\), as \(d\leq n\), which is the time-complexity of the method in worst-case.