Gadget testing A firm wants to determine the highest floor o

Gadget testing A firm wants to determine the highest floor of its n-story headquarters from which a gadget can fall without breaking. The firm has two identical gadgets to experiment with. If one of them gets broken, it cannot be repaired, and the experiment will have to be completed with the remaining gadget. Design an algorithm in the best efficiency class you can to solve this problem.

Can someone give me a complete algorithm to solving this problem instead of an explanation. it can be done in sqrt(n) we know that.

Solution

We could start at the first floor and check every floor following it upwards. Then we do not need two gadgets. The

best-case is when gadget breaks at first floor. The worst-case is when the gadget first breaks at the n-t h floor. No

other method’s best-case is better than this one. But we are usually more concerned about the worst-case

(average-case is more important but it is hard to analyze). So, we shall try to improve the worst-case as we have

more than one gadget.

In order to minimize the number of required drops, we should make big jumps. But when the first gadget breaks, we

fall back to linear search for the “jump” number of floors in the worst-case. So, we Should hit an optimal trade-off

between number of jumps and jump-length. Say, jump length is j. Then in the worst-case we need to make n j

jumps and following that we have to perform linear search of length j. The optimal point is when n j = j or j =n. So,

we drop the first gadget from the b n c-t h floor and if it doesn’t break, move to the 2 · b n c-t h floor, and so on.

When the first gadget breaks, we have to do b n c drops with the second gadget in the worst-case. So, the

algorithm is in O( n).