# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 4 Same Cluster Queries
### An Algorithm Using Few SCQs
#### 4.2.2 Extensions of Theorem 5  
In the algorithm presented above, we need to set a parameter \(n_{1}\) and then the algorithm works for all inputs where the smallest cluster has a size of at least \(n_{1}\). We next observe that this prior knowledge is _not_ needed in Step 1 of the algorithm, and that Step 2 can be modified to work without this assumption on the input. Specifically:  
1. Lemma 12 still holds since in Step 1 we simply continue extracting random points until every cluster has at least one point. As already observed, we can safely extract points _with_ replacement as in the CCP problem since extracting the same point more than once has no effect on the stopping condition. Therefore, all upper bounds on the CCP problem also apply (see Lemma 11).
2. In Step 2, we can use _high-cost_ comparisons to assign every point to its correct cluster. Since these operations are always correct, we no longer need \(C=\Omega(\log n)\) points per cluster, and can in fact reduce them to \(C^{\prime}=\Theta(\sqrt{\log n})\), which is the number we need in Step 3 to have a high-probability of success. Selecting \(m^{\prime}\geq 2C^{\prime}/p_{1}\) points guarantees that the probability that not all clusters have at least \(C^{\prime}\) points is at most \(q(m^{\prime})=k\exp(-\frac{C^{\prime}}{4})=k\exp(-\frac{p_{1}m^{\prime\prime} }{8})\). For a suitable \(m^{\prime}=\Theta(\frac{\log k}{p_{1}})\), this probability is constant, say \(q(m^{\prime})<1/3\). Therefore, in expectation, we have to wait a constant number of \"rounds\" of \(m^{\prime}\) extractions each, meaning that the number of extractions needed before reaching \(C^{\prime}\) points in each cluster is \(O(m^{\prime})=O(\frac{C^{\prime}+\log k}{p_{1}})\). Since for every point we have to check all clusters, the expected high-low cost operations of Phase 2 is \(O\left\langle k\frac{\sqrt{\log n}+\log k}{p_{1}},0\right\rangle\).
3. Step 3 is as before and it takes \(O\left\langle 0,kn\log n\right\rangle\) high-low cost operations. Its success probability is at least \(1-\frac{1}{n}\), while the two previous steps are always successful since we use high-cost operations. This leads to the following extension of Theorem 5:  
**Theorem 6**.: _For any \(\gamma\)-perturbation-stable metric space \((X,d)\) which has \(\gamma\)-radius optimal clusters, \(\gamma\geq 2\), the optimal \(k\)-clustering can be computed using only the following number of exact same-cluster queries and high-low cost operations parameterized in \(p_{1}=\frac{n_{1}}{n}\), where \(n_{1}\) is the size of the smallest optimal cluster:_  
1. _The algorithm uses_ \(O(k\mathcal{C}(\mathbf{p}))\leq O(\frac{k\log k}{p_{1}})\) _exact same-cluster queries in expectation, where_ \(\mathbf{p}\) _depends on the size of the optimal clusters (Lemma_ 11_), and_ \(\mathcal{C}(\mathbf{p})\) _is the corresponding coupon collector bound (Lemma_ 12 _and Observation_ 6_)._The additional high-low cost operations used by the algorithm is  
\[O\bigg{\langle}k\frac{\sqrt{\log n}+\log k}{p_{1}},kn\log n\bigg{\rangle}. \tag{11}\]  
If the size of the smallest cluster is known, then the high-low cost upper bound in (7) also applies.