Highest Safe rung problem : There are many rungs on a ladder in increasing order of height. A bottle is thrown from a rung, and depending on the height of the rung, the bottle may break or may not (bottle breaks for higher height rungs, and doesn't for lower rungs). We need to find the maximum height safe rung for which the bottle doesn't break given that:
(1) We have only 1 bottle with us.
(2) We have infinite bottles with us.
(3) We have exactly 2 bottles with us.
(4) We have k bottles with us. ($1 \leq k$).
Design algorithms for solving (1) - (4) in best possible time complexity. (Also note that (3) and (4) should be an asymptotic improvement over (1).]
My method: (1) is just a linear search and (2) is a divide and conquer approach to solving the problem. I cannot find an asymptotically improved algorithm for (3) - the only methods which I kept thinking of provide some constant factor improvements in time complexity over (1), I am absolutely clueless on how to solve for (3) and (4).
P.S: This is a problem from Chapter 1 of Kleinberg and Tardos. I couldn't find it's solution online.