1
$\begingroup$

I'm going through the problems of the Brute Force chapter from Introduction to Analysis and Design of Algorithms by A.Levitin. One problem solution caught my eye, though.

The problem states as follows:

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.

The brute force approach is quite obvious (try every floor until the first gadget breaks). However, I can't come to terms with the efficient one (which I found googling).

  • Throw the first gadget every multiple of $\sqrt{N}$

  • If the gadget breaks at $i*\sqrt N $, then the upper bound will be between $(i-1)*\sqrt{N}$ and $i*\sqrt{N} -1$

  • Details aside, the overall complexity is $O(\sqrt{N})$

My question is how do you come up with $\sqrt N $? Why is it better than say: trying every even or odd floor?

$\endgroup$

1 Answer 1

1
$\begingroup$

Maybe it would be interesting to start with a restriction of the problem where you have only one gadget.

In order to find the highest floor from which you can drop it, you must do you tries from the lowest floor, increasing the floor you drop the gadget from by one each time. If you try something else, the gadget could break before you identify the highest floor, so it is the only viable strategy. It is clear that this strategy is in $\Theta(N)$ in the worst case.

Now let's look at the strategy you propose for two gadget:

trying every even or odd floor

Since the number of even (or odd) floors is at least $\left\lfloor \frac{N}2\right\rfloor$ this strategy is also in $\Theta(N)$ in the worst case.

To explain the idea of the $\mathcal{O}(\sqrt{N})$ strategy, think of it this way:

  • decompose the $N$ floors into (more or less) $\sqrt{N}$ groups of $\sqrt{N}$ consecutive floors ;
  • the first gadget is used to find the highest group from which you can drop it, similarly to the one-gadget-strategy (time $\mathcal{O}(\sqrt{N})$) ;
  • the second gadget is used to find the highest floor in the previous group from which you can drop it, similarly to the one-gadget-strategy (time $\mathcal{O}(\sqrt{N})$).

The overall time is indeed $\mathcal{O}(\sqrt{N})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.