An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
This work provides a more efficient solution for a classic sequential decision-making problem, relevant to operations research and algorithm design.
The paper presents an algorithm for the generalized egg dropping problem that achieves O(log N) time complexity, improving over the previous O(K log N) approach, by using a restricted binary search over multiples of K and an incremental traversal.
The generalized egg dropping problem is a classic challenge in sequential decision-making. Standard dynamic programming evaluates the minimax minimum number of tests in $\mathcal{O}(K \cdot N^2)$ time. A known approach formulates the testable thresholds as a partial sum of binomial coefficients and applies binary search to reduce the time complexity to $\mathcal{O}(K \log N)$. In this paper, we demonstrate that binary search over the complete sequential test domain is suboptimal. By restricting a binary search over multiples of $K$, we isolate a dynamic structural envelope that guarantees convergence. We prove that this boundary balances the search depth against the combinatorial evaluation cost, cancelling the $K$ variable to strictly bound the search phase to $\mathcal{O}(\log N)$. Combined with an incremental traversal, our algorithm eliminates the standard bottlenecks. Furthermore, we formulate an explicit $\mathcal{O}(1)$ space policy to dynamically reconstruct the optimal decision tree.