What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?

Question

Background:

The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half).

Pool Ball Problem: Given $n$ pool balls where exactly 1 weighs more than the rest, find that pool ball using a scale.

The common approach is to split the balls into two groups, then weighing each group. You can narrow it down to one ball in roughly $\log_2(n)$ rounds. You can modify the algorithm to change the resulting base of the logarithm. This can be done by changing how many groups the scale can weigh. For example, if you had a scale that determined the heaviest of 4 groups (plus sign shaped on a pivot), then you would only need roughly $\log_4(n)$ rounds.

---

Problem: Consider the pool ball weighing problem but allow us to grow the number of groups we can split the set of pool balls into.

Instead of using a scale that compares a predetermined constant number, $k$, of pool ball groups, suppose we are allowed to vary and modify it during execution. For example, you are allowed to start with a split into 2 groups, then 3 groups next round, then 4, etc. It is not bounded apriori. Let's say that comparing $k$ groups takes $O(k)$ time. As a result, we know the heaviest of the $k$ groups or know if they weigh the same. If we grow the number of splits with each successive round, then we would require much fewer than $log(n)$ weigh-ins. There are divisibility issues that come up when doing the splits, but assume they are trivial to resolve.

$f(i) = \text{# of splits in $i^{\text{th}}$ round}$ (This is a positive, increasing function. We are required to spend the time/space to compute this.)

Let $t_f(i)$ be the time complexity of computing $f(i)$ given $\langle f(1), \dots, f(i-1)\rangle$ or subset of.

$N(i) = \begin{cases} n & \text{if } i = 0 \\ \frac{N(i-1)}{f(i)} & \text{if } i \geq 1 \end{cases} = \text{# of pool balls after round $i$}$

We narrow our search down to one ball in $j$ rounds when: $N(i) = 1 \geq \frac{n}{f(1)\cdot f(2)\cdot \dots \cdot f(j)}$

Or alternatively:

$\prod_{k=0}^{j}f(k) \geq n$ for some $j(n)$ dependent on $f$

Question: What can we say for the optimal time complexity of this algorithm? What are some properties of an optimal $f(i)$ we should expect? I realize this heavily depends on which models of computation we use (computing a fast growing $f$ can be expensive on some models while cheap on others). I'm willing to be reasonably flexible and not picky about it. Perhaps you guys could suggest a fruitful/interesting choice. For instance, the undergrad version of the problem trivializes the complexity by ignoring the complexity of grouping the balls together and probably considers $+, \times$ to take constant time.

The tricky part here is to pick a fast growing $f(i)$ that does not end up becoming too expensive to compute. The faster a chosen $f$ grows, the more that the time complexity decreases. On the flip side, the longer $f$ takes to compute, the longer the algorithm ends up running. We're looking for ways to balance these two.

Example: I could simply increment the number of groups I split the pool balls into each round. Here, $f(i) = i + 1$. The total number of uses of the scale is $O(\Gamma^{-1}(n))$ (inverse factorial). The overall asymptotic time complexity is $(2+3+\dots+\Gamma^{-1}(n)) + \Gamma^{-1}(n) = O\left( \binom{\Gamma^{-1}(n)}{2} \right)$ (this takes into account the time complexity of handling the k-scale and incrementing the number of rounds each time). I'm assuming integer addition is a constant time operation.

Answer 1

The asymptotically optimal algorithm is to split in 2 groups at each step. In other words, the ability to split into more than 2 groups does not allow us to find an asymptotically more efficient algorithm.

Suppose we split into $k$ at each step. Then we get an algorithm whose running time is given by the following recurrence relation:

$$T(n) = T(n/k) + O(k).$$

We do $\lg(n)/\lg(k)$ recursive calls to reach the base case, so the solution to this recurrence relation is

$$T(n) = O(k \lg(n)/\lg(k)).$$

Now the function $f(k) = k / \lg(k)$ attains its minimum at $k=2$; for larger $k$, it is strictly increasing. Therefore, the optimal choice of $k$, if we split by the same ratio at each level and disregard constant factors, is $k=2$.

Splitting by a different amount at each level doesn't help. The above argument applies to all $n$, so it applies no matter the number of balls -- i.e., no matter what level we split at.

---

Here is another way to think about it. Suppose we split into $k_1,k_2,k_3,\dots,k_m$ groups at each level ($k_1$ groups in the first call, $k_2$ in the second recursive call, and so on). Let's count the number of bits of information we've gained.

How many bits of information do we get after applying the scale when we've split into $k$ groups? $\lg k$ bits of information, since there were $k$ possibilities. So, we get $b_i$ bits of information at the $i$th call, where $b_i= \lg k_i$.

Now we need a total of $\lg n$ bits of information to uniquely identify the ball. Therefore, we need to select $b_1,\dots,b_m$ so that

$$b_1 + b_2 + \dots + b_m \ge \lg n.$$

What is the running time for any particular choice of $b_1,\dots,b_m$? Well, in the $i$th call, we split into $k_i = 2^{b_i}$ groups, and the time to use the scale is $O(k_i)$, i.e., $O(2^{b_i})$. Therefore, the total running time for a particular choice of $b_1,\dots,b_m$ is

$$O(2^{b_1} + 2^{b_2} + \dots + 2^{b_m}).$$

Now we want to find the optimal choice of $b_1,\dots,b_m$. This requires us to minimize $2^{b_1} + + \dots + 2^{b_m}$ subject to the constraint that $b_1 + \dots + b_m \ge \lg n$. One can compute that the minimum is attained for $b_1= \dots = b_m = 1$.

---

At the end of your post, you propose an algorithm that increments the number of splits at each step. You didn't compute the asymptotic running time of your algorithm or compare it to binary search, but if carry through that analysis, it turns out that your algorithm is asymptotically slower than binary search. Therefore, your proposed algorithm is worse than straightforward binary search. It does not contradict any of the above analysis.

Details: By Stirling's approximation, $\Gamma^{-1}(n) = O(\lg n)$ (roughly, ignoring log-log factors), so your proposed algorithm's running time is something like $O((\lg n)^2)$ (roughly, ignoring log-log factors), i.e., worse than binary search.