I had to answer these questions for an algorithm analysis course Im currently taking. Im not sure if the answers I have here are sufficiently valid/correct to satsify as a solution. I would appreciate it if anyone would be able to critique my solutions :) Q: Suppose that you have an N story building and supply of filled water balloons. Suppose also that a water balloon breaks if it is dropped off of floor F or higher, and survives otherwise. Devise a strategy to determine the floor F using at most 1 + lg N drops. A: For this, we would just use a binary search, since the runtime of a binary search is O(logN), which is equal to O(1 + lgN) = O(lgN) = O(logN) Q: Repeat the previous question, but devise a strategy that uses only O(log F) drops. A: First, given an N story building, let us represent each interval of floors by 2^k, where k is the floor at which a water balloon is dropped. If the balloon breaks at a floor 2^k, we know that the balloon will NOT break when dropped at 2^(k-1) floor. Therefore, we can conclude the floor F is 2^k < F < 2^(k-1). Using this inequality: 2^k < F < 2^(k-1) => k-1 < lgF < k => k-1 < lgF => k < lgF + 1 => O(lgF) Finally, we can use a binary search to find our floor F. 2^k - 2^(k-1) = 2*2^(k-1) - 2^(k-1) = 2^(k-1) + 1 = lg2^(k-1) + 1 = k-1 => O(lgF), therefore the # of drops k = O(lgF) Q: Repeat the previous question, but assume you only have two water balloons. Now your goal is to minimize the number of drops. Of course, once you break a water balloon, you can't use it again. Devise a strategy to determine F that involves O(sqrt(N)) drops and guarantees to find F. EXTRA: Do it with only O(sqrt(F)) drops. A: Let N = total # of floors of the building. Let sqrt(N) = interval of floors, with each interval containing sqrt(N) floors. Let k = floor at which the balloon is dropped (or, # of drops, since we will progress linearly floor by floor) since there are sqrt(N) floor intervals: k*sqrt(N) = n for (k=1, 2, 3...sqrt(N)) therefore, at a maximum: k = sqrt(N), which implies k*sqrt(N) = sqrt(N)*sqrt(N) = N since the number of drops k is at most sqrt(N), we conclude k = O(sqrt(N)) For that last question, Im not completely confident my solution is correct. Also, how would I do it with only O(sqrt(F)) drops?

From the forum FAQ:

9. Do not ask homework related questions. The Gamedev.net members are not here to answer your homework questions, its against the forum rules and few people take kindly to it. Besides, we shouldn't need to tell you that figuring it out for yourself will be way more beneficial to you in the long run.