Question

Design and Analysis of Algorithms: Gadget Testing A company wants to determine the highest floor of its n-story headquarters from which a gadget can fall without breaking, so they’ll test this by dropping gadgets and seeing when they break. The company only has one gadget to test with, and if the gadget breaks, it cannot be repaired – that is, by the time the gadget breaks, they better have the answer to your question. Hint:Solve a simpler problem with a single gadget first. Then design a better
than linear algorithm for the problem with two gadgets.

1. (brute force) Design a Θ(n)-time algorithm to solve this problem. Provide pseudocode or a precise description of your approach. Determine the worst-case efficiency of your algorithm as a function of n, the number of stories of the building.

(b) (optimization) Now, suppose that the company has two identical gadgets to experiment with (identical means that if gadget 1 could survive a fall from floor k, then so can gadget 2, and vice-versa). If one of the gadgets gets broken, it cannot be repaired, and the experiment will have to be completed with the remaining gadget. Use the 2nd gadget to improve on your algorithm from part (a). That is, design an algorithm that has efficiency better than Θ(n). (How do do find the time complexity for this algorithm)

Answer 1

The two parts of the algorithm are given in handwritten format.