In the Egg Drop problem, we are given some number of eggs (k), and we are tasked with finding the

This problem has been solved!

Do you need an answer to a question different from the above? Ask your question!

Question:

In the Egg Drop problem, we are given some number of eggs (k), and we are tasked with finding the highest floor of an n-story building from which we can drop an egg without breaking. The Egg Drop problem asks us to find the fewest number of egg dropping trials we need to perform in the worst case in order to identify this floor on an n-floor building when given k eggs. The cost of the algorithm, to be kept minimal, is expressed as the number of eggs that are thrown (note that re-use is allowed).

QUESTION: Find a solution to the Egg Drop Problem in O(k + n/(2^(k-1))) eggs thrown. (HINT: You may consider using a combination of different searching strategies, such as binary search, linear search, etc. One strategy is used to find the segment, the other one is used to target the exact floor within the segment. Actually, that is the reason why you have an "+" within O(k + n/(2^(k-1))), the two complexity components come from two different searching strategies.)