# A Mixed Clustering Approach for Real-Time Anomaly Detection
## 5 Time Complexity  
To calculate the time complexity, the following steps are taken. Since the data are real time, it is quite difficult to prefix the number of data instances. Without loss of generality, it is assumed that the data are finite, let it be \(n\). Let \(k\) (\(\leq\)\(n\)) be the number of clusters, \(d_{\rm n}\) = no of numeric attributes, and \(d_{\rm c}\) = no of categorical attributes so that \(d=d_{\rm n}+d_{\rm c}+1\) = the total number of attributes, where the extra attribute is the time attribute. The computational cost for calculating centroid is O(\(n+n.k.d_{\rm n}\)). The computational cost for step1, step2, and step 3 is O(\(n.k.d_{\rm n}\)). Step 4 takes O(\(k.n+n.k\)) time, as for each centroid, the distance of the data instance has to be computed, and minimum distance has to be chosen to assign the data instance in that cluster. The O(\(n.k\)) time is needed to compute the minimum distance for each \(k\)-clusters. Since each data instance is associated with a time stamp it needs another O(\(n.k\)) time. The cost of updating the two matrices along with lifetimes of clusters is O(\(3.k\)). This is the computational cost of step 5. Moreover, the computational cost of updating the weights of categorical attributes is O(\(a.n.k.d_{\rm c}\)), where \(a\) = average number of possible values that the categorical attributes can take. Thus, the total computational cost of step 4 and step 5 is O(\(3.k+2\)\(n.k+a.n.k.d_{\rm c}\)) = O(\(a.n.k.d_{\rm c}\)). If \(i\) is the number of iterations, then the total computational cost for phase-1 is O(\(i.(n.k.d_{\rm n}+a.n.k.d_{\rm c})\)) = O(\(i.a.n.k.d_{\rm c}\)). For phase-2, the clusters obtained during phase-1 are to be merged based on similarity measure and the non-empty intersection of lifetimes or core(lifetimes). For merging two clusters with lifetimes requires O(\(n_{1}.n_{2}\)); where \(n_{1}\) and \(n_{2}\) are the sizes of the two clusters to be merged. Additionally, merging is associated with the superimposition of the cluster's lifetimes. Let \(m_{1}\) be the number of intervals superimposed in the lifetime of one cluster and \(m_{2}\) be the number of intervals superimposed in the lifetime of another cluster and their cores have non-empty intersections. For the intersection of cores O(1) time is required. Ifsuperimposed intervals is to be superimposed on \(m_{2}\) such that \(m_{1}\leq n\) and \(m_{2}\leq n\), then the boundaries of \(m_{1}\) are to be inserted on that of \(m_{2}\) as two sorted arrays. So, this is basically merging four sorted arrays to produce two sorted arrays one for left end points and others for right end points. The searching in four sorted array requires O(log\(m_{1}\) + log\(m_{2}\) + log\(m_{1}\) + log\(m_{2}\)) = O(4 log\(n\)) = O(log\(n\)) time as \(m_{1}\) = O(\(n\)) and \(m_{2}\) = O(\(n\)). The insertion in sorted arrays will require O(\(m_{1}\) + \(m_{2}\) + \(m_{1}\) + \(m_{2}\)) = O(4.\(n\)) = O(\(n\)). If \(t\) is the number of iterations in phase-2, the total cost will be O(\(t\)(log\(n\) + \(n\))) = O(\(k\).log\(n\) + \(k.n\)), as \(t\leq k\). The total cost of all the steps is O(\(i.a.n.k.dc\) + \(k\).log\(n\) + \(k.n\)). Since \(k\) is constant \(d_{c}\leq n\), \(i\leq k\leq n\), \(a\leq n\), \(i\) is also constant. The overall complexity of the algorithm is O(\(n.n.n\)) = O(\(n^{3}\)), which shows the efficacy of the algorithm.