Paper
An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
Authors
Kleitos Papadopoulos
Abstract
The generalized egg dropping problem is a canonical benchmark in sequential decision-making. Standard dynamic programming evaluates the minimum number of tests in the worst case in $\mathcal{O}(K \cdot N^2)$ time. The previous state-of-the-art approach formulates the testable thresholds as a partial sum of binomial coefficients and applies a combinatorial search to reduce the time complexity to $\mathcal{O}(K \log N)$. In this paper, we demonstrate that the discrete binary search over the decision tree can be bypassed entirely. By utilizing a relaxation of the binomial bounds, we compute an approximate root that tightly bounds the optimal value. We mathematically prove that this approximation restricts the remaining search space to exactly $\mathcal{O}(K)$ discrete steps. Because constraints inherently enforce $K < \log_2(N+1)$, our algorithm achieves an unconditional worst-case time complexity of $\mathcal{O}(\min(K, \log N))$. Furthermore, we formulate an explicit $\mathcal{O}(1)$ space deterministic policy to dynamically retrace the optimal sequential choices, eliminating classical state-transition matrices completely.
Metadata
Related papers
Fractal universe and quantum gravity made simple
Fabio Briscese, Gianluca Calcagni • 2026-03-25
POLY-SIM: Polyglot Speaker Identification with Missing Modality Grand Challenge 2026 Evaluation Plan
Marta Moscati, Muhammad Saad Saeed, Marina Zanoni, Mubashir Noman, Rohan Kuma... • 2026-03-25
LensWalk: Agentic Video Understanding by Planning How You See in Videos
Keliang Li, Yansong Li, Hongze Shen, Mengdi Liu, Hong Chang, Shiguang Shan • 2026-03-25
Orientation Reconstruction of Proteins using Coulomb Explosions
Tomas André, Alfredo Bellisario, Nicusor Timneanu, Carl Caleman • 2026-03-25
The role of spatial context and multitask learning in the detection of organic and conventional farming systems based on Sentinel-2 time series
Jan Hemmerling, Marcel Schwieder, Philippe Rufin, Leon-Friedrich Thomas, Mire... • 2026-03-25
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2602.22870v1</id>\n <title>An $\\mathcal{O}(\\log N)$ Time Algorithm for the Generalized Egg Dropping Problem</title>\n <updated>2026-02-26T11:08:37Z</updated>\n <link href='https://arxiv.org/abs/2602.22870v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2602.22870v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>The generalized egg dropping problem is a canonical benchmark in sequential decision-making. Standard dynamic programming evaluates the minimum number of tests in the worst case in $\\mathcal{O}(K \\cdot N^2)$ time. The previous state-of-the-art approach formulates the testable thresholds as a partial sum of binomial coefficients and applies a combinatorial search to reduce the time complexity to $\\mathcal{O}(K \\log N)$. In this paper, we demonstrate that the discrete binary search over the decision tree can be bypassed entirely. By utilizing a relaxation of the binomial bounds, we compute an approximate root that tightly bounds the optimal value. We mathematically prove that this approximation restricts the remaining search space to exactly $\\mathcal{O}(K)$ discrete steps. Because constraints inherently enforce $K < \\log_2(N+1)$, our algorithm achieves an unconditional worst-case time complexity of $\\mathcal{O}(\\min(K, \\log N))$. Furthermore, we formulate an explicit $\\mathcal{O}(1)$ space deterministic policy to dynamically retrace the optimal sequential choices, eliminating classical state-transition matrices completely.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='cs.DS'/>\n <published>2026-02-26T11:08:37Z</published>\n <arxiv:primary_category term='cs.DS'/>\n <author>\n <name>Kleitos Papadopoulos</name>\n </author>\n </entry>"
}