# AutoElbow: An Automatic Elbow Detection Method for Estimating the Number of Clusters in a Dataset
## 3 AutoElbow Method
### Time Complexity  
In this section, we provide the time complexity (TC) of both the AutoElbow algorithm and the iterated K-means algorithm, based on the pseudocodes of Algorithms 1 and 2, respectively. First, it should be noted that Algorithm 1 implements the iteration of the K-means algorithm towards computing the elbow-based graph. In order to accomplish this, Algorithm 1 calls a single _for_-loop between steps 2 and 7, thus, yielding a TC of \(O(K)\), where \(K\) is the total number of anticipated clusters in the dataset. However, because the basic K-means algorithm has a TC of \(O(N^{2})\)[19], where \(N\) is the total number of data points, the overall TC of Algorithm 1, thus, reduces to \(O(KN^{2})\).  
The AutoElbow method in Algorithm 2 also adopts a single _for_-loop based on the outcome of the conditional concavity test of step 3. As a result, the single _for_-loop is executed towards computing the parameters of Equation (10) as seen in steps 7-10, 15-18, 23-26, and 31-34 of Algorithm 2. Hence, the TC of the AutoElbow algorithm approaches \(O(K)\) asymptotically. Consequently, when considered independently of Algorithm 1, the AutoElbow method is indeed a fast algorithm, as \(K\) is often considered a small number (K < 100) based on the application area. However, when both the iteration of the K-means algorithm and the AutoElbow technique are executed sequentially, we obtain an overall TC of \(O(KN^{2})+O(K)\).  
```
1:Data \(Z\), The maximum number of potential clusters \(K\);
2:Elbow graph, \(G\);
3:\(G\leftarrow[\;]\;\;\) Initialize \(G\) as an empty set
4:for\(k=1\) to \(K\)do
5:\([z_{i}^{(k)},c_{k}]\leftarrow\)K-means(\(Z,k\))  Run K-means algorithm with \(k\) as number of clusters
6: Compute \(y_{k}\) (i.e., TWSD) using (1)
7:\(x_{k}=k\)
8:\(g_{k}\leftarrow[x_{k},y_{k}]\)
9:\(G\leftarrow[G,g_{k}]\)  Append (i.e., save) graph points \(g_{k}\) into \(G\)
10:endfor
11:Return \(G\)
```  
**Algorithm 1** Generate elbow graph \(G\)  
```
1:Graph \(G\);
2:Estimated number of clusters \(k^{*}\);
3:\(K\leftarrow\) length(\(G\))
4:Normalize \(G\) as \(G^{norm}\) (see (2)) using (3) and (4)
5:Check for the concavity \(\mathcal{C}\) of \(G^{norm}\) using (7)
6:if \(\mathcal{C}==1\)then
7:\(-\) left elbow graph \(-\)
8: Clean up \(G^{norm}\) using (8)
9:for\(k=1\) to \(K\)do
10: Compute \(a_{k},b_{k}\), and \(c_{k}\) using (17), (18), and (19), respectively
11: Compute \(f_{k}\) using (10)
12:endfor
13:Obtain \(k^{*}\) using (23)
14:elseif\(\mathcal{C}==2\)then
15:\(-\) right elbow graph \(-\)
16: Clean up \(G^{norm}\) using (9)
17:for\(k=1\) to \(K\)do
18: Compute \(a_{k},b_{k}\), and \(c_{k}\) using (20), (21), and (22), respectively
19: Compute \(f_{k}\) using (10)
20:endfor
21:Obtain \(k^{*}\) using (23)
22:elseif\(\mathcal{C}==3\)then
23:\(-\) left knee graph \(-\)
24: Clean up \(G^{norm}\) using (9)
25:for\(k=1\) to \(K\)do
26: Compute \(a_{k},b_{k}\), and \(c_{k}\) using (11), (12), and (13), respectively
27: Compute \(f_{k}\) using (10)
28:endfor
29:Obtain \(k^{*}\) using (23)
30:elseif\(\mathcal{C}==4\)then
31:\(-\) right knee graph \(-\)
32: Clean up \(G^{norm}\) using (8)
33:for\(k=1\) to \(K\)do
34: Compute \(a_{k},b_{k}\), and \(c_{k}\) using (14), (15), and (16), respectively
35: Compute \(f_{k}\) using (10)
36:endfor
37:Obtain \(k^{*}\) using (23)
38:elseif\(\mathcal{C}==4\)then
39:\(-\) right knee graph \(-\)
40: Clean up \(G^{norm}\) using (8)
41:for\(k=1\) to \(K\)do
42: Compute \(a_{k},b_{k}\), and \(c_{k}\) using (14), (15), and (16), respectively
43: Compute \(f_{k}\) using (10)
44:endfor
45:Obtain \(k^{*}\) using (23)
46:endif
47:Return \(k^{*}\)
```  
**Algorithm 2** AutoElbow method