Time-Space Tradeoffs for the Memory Game
summary
Deterministic algorithms that only compare cards for equality achieve a pass-based tradeoff with a simple upper bound s·T = n^2, and a matching lower bound (up to logs) is proved using a branching program model, stage decomposition and an adversarial counting argument. Allowing arithmetic and randomness weakens the proven lower bound to s·T^2 = Ω(n^3), proved by unfolding a stage, setting R ≈ √(nT), and applying Chernoff/negative-association tail bounds. Open questions: whether the stronger s·T = Ω(n^2) holds for randomized or more general models and whether upper-bound techniques (Floyd-style collision finding) can close the gap.
AI-written summary · about