1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The runtime of the algorithm also heavily depends on the number of rounds we end up needing ($m$). I'm under the impression that we need to reduce it, too, along with the minimization that you are doing. The procedure for generating the sequence $\lbrace k_i \rbrace$, which yields $\lbrace b_i \rbrace$, influences how necessarily large $m$ ends up being. In the predetermined constant number of splits case that you suggest, wouldn't $m$ be more or less maximized? $\endgroup$ – mdxn Sep 5 '14 at 6:30
  • $\begingroup$ @mdx, that's already taken into account in my formalization. Actually, I showed two separate, independent lines of reasoning to justify my answer. Both lines of reasoning take that into account. The recurrence relation $T(n)$ takes into account the total running time (which is roughly speaking the time per iteration times the number of iterations; $m$ is the number of iterations). The second approach is a minimization over all $b_1,\dots,b_m$, where $m$ is allowed to vary (it is not fixed in advance), so it also takes this into account. Thus, these minimize total running time. $\endgroup$ – D.W. Sep 5 '14 at 15:44
  • $\begingroup$ What would be the flaw in the logic behind the example I provided at the end of the post then? $\endgroup$ – mdxn Sep 5 '14 at 15:46
  • $\begingroup$ @mdx, why do you think there is a flaw in the logic behind that example? $\endgroup$ – D.W. Sep 5 '14 at 15:49
  • $\begingroup$ @mdx, hint: try calculating the asymptotic running time of the example algorithm you provided at the end of your post, and compare it to standard binary search. What do you get? By Stirling's approximation, $\Gamma^{-1}(n) = O(\lg n)$ (roughly, ignoring log-log factors), so your algorithm's running time is something like $O((\lg n)^2)$ (roughly, ignoring log-log factors), i.e., worse than binary search. So as far as I know there is no flaw in your algorithm or your analysis; it is correct, but your proposed algorithm is slower than binary search. $\endgroup$ – D.W. Sep 5 '14 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.