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.

$($brute force$)$ Design a $\backslash$Theta $($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 $2$nd gadget to improve on your algorithm from part $($a$).$ That is$,$ design an algorithm that has efficiency better than $\backslash$Theta $($n$).$