In first steps in algorithmic design and analysis I am following the book Algorithm Design by Kleinberg and Tardos I came across the Question/Case you can find down the page the solution is indeed f(n) = sqrt(n). My concerns are :
1- Why I still find log(n) more acceptable .I still could not grasp the plus value from sqrt(n) even when it is said that we will use more jars / trials .
2- from where did we get the sqrt(n) ?. Using k jars (trials) I could think of n/k incrementation but then lim n→∞ f(n) /n toward infinity is 1/k which is not 0. I got the feeling that the '2' in n^1/2 is tightly related to k = 2 , if yes how.
Thank you.
Case: Assume that a factory is doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung. It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung n/4 or 3n/4 depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer. If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it n times. So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of k ≥ 1 jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most k jars in doing so. Now, please solve these two questions:
- Suppose you are given a budget of k = 2 jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most f(n) times, for some function f(n) that grows slower than linearly. (In other words, it should be the case that lim n→∞ f(n)/n = 0.)