I tend to think it is. With one jar, we must drop a jar at most n times, but we only break at most one jar. This is the best case if you want to break the fewest jars, but the worst case in terms of time. With infinite jars, we must drop a jar at most logn times, and we break at most logn jars. This is the best case in terms of time, but the worst case in terms of jars.
So I don't think it's possible to get a better solution than logn (in terms of time). If you have logn jars, then you'll have logn time. If you have log(n)+1 jars, you'll STILL have logn time.
i agree with Stephen, that the best algorithm for finding the rung when you have as many jars as you need is binary search. It is also what the book seems to be suggesting.
it seems our function should shift from O(n) when k=1 to O(logn) when k >= logn
Actually, if you add threads to the problem you can achieve constant time. Just have one person (thread) drop a jar from each rung, and keep track of it to see if it breaks or not.
It's right that log(n) is the best you can do, given infinitely many jars. However, in answer to Mark's suggestion, you should not expect log(n) to fall out of your answer to the problem for finite values of k. The reason has to do with the approximation one is doing using the big-O/Omega/Theta notation. Specifically, when you show the number of drops is O(f_k(n)), for, say, k=3, the hidden constant in the big-O is actually a function of k. When k is not a constant, such as k=log n, it is no longer ok to hide this function of k in the big-O notation, because it isn't a constant anymore.
If you find that confusing, don't worry. But don't expect to see anything like log(n) in your solution.
Also, for a hint, if I give you 2 jars, how many rungs can you handle with 1 guess, 2 guesses, 3 guesses, 4 guesses, 5 guesses? Work this out by hand. Can you see the pattern? Can you write down the function R(g), that tells how many rungs R for g guesses? Is this function Theta(some simpler function)? The answer you seek is the inverse of this function (like in problem 2.7).
Finally, @spatel, what you are talking about is not threads, but parallel processors. You would need one processor (or core) for every rung. Multi-threading is necessary to take advantage of the multiple processors, but you mostly see it used on conventional computers, to facilitate timesharing of the one (or few) processor(s).
I don't think there's any way to get a better runtime than O(n) if you only have one jar. To get a better runtime than O(n) you'd have to skip rungs to get some runtime less than O(n), but this means if you have one jar, and you skip rungs, you run the risk of breaking your jar and not knowing the highest rung it can be safely dropped at, so the algorithm would have no way of returning a specific rung, which would be an invalid solution.
Is the binomial search the theoretical best for this problem (yielding log(n))?
ReplyDeleteGood question. Anyone from the class want to reply?
ReplyDeleteI tend to think it is.
ReplyDeleteWith one jar, we must drop a jar at most n times,
but we only break at most one jar. This is the best case if you want to break the fewest jars, but the worst case in terms of time.
With infinite jars, we must drop a jar at most logn times, and we break at most logn jars. This is the best case in terms of time, but the worst case in terms of jars.
So I don't think it's possible to get a better solution than logn (in terms of time). If you have logn jars, then you'll have logn time. If you have log(n)+1 jars, you'll STILL have logn time.
i agree with Stephen, that the best algorithm for finding the rung when you have as many jars as you need is binary search. It is also what the book seems to be suggesting.
ReplyDeleteit seems our function should shift from O(n) when k=1 to O(logn) when k >= logn
-Mark S Montoya
Actually, if you add threads to the problem you can achieve constant time. Just have one person (thread) drop a jar from each rung, and keep track of it to see if it breaks or not.
ReplyDelete/troll
It's right that log(n) is the best you can do, given infinitely many jars. However, in answer to Mark's suggestion, you should not expect log(n) to fall out of your answer to the problem for finite values of k. The reason has to do with the approximation one is doing using the big-O/Omega/Theta notation. Specifically, when you show the number of drops is O(f_k(n)), for, say, k=3, the hidden constant in the big-O is actually a function of k. When k is not a constant, such as k=log n, it is no longer ok to hide this function of k in the big-O notation, because it isn't a constant anymore.
ReplyDeleteIf you find that confusing, don't worry. But don't expect to see anything like log(n) in your solution.
Also, for a hint, if I give you 2 jars, how many rungs can you handle with 1 guess, 2 guesses, 3 guesses, 4 guesses, 5 guesses? Work this out by hand. Can you see the pattern? Can you write down the function R(g), that tells how many rungs R for g guesses? Is this function Theta(some simpler function)? The answer you seek is the inverse of this function (like in problem 2.7).
Finally, @spatel, what you are talking about is not threads, but parallel processors. You would need one processor (or core) for every rung. Multi-threading is necessary to take advantage of the multiple processors, but you mostly see it used on conventional computers, to facilitate timesharing of the one (or few) processor(s).
Can we reduce the algorithm from O(n) to some better time, if we have only 1 jar?
ReplyDeleteLucia,
ReplyDeleteI don't think there's any way to get a better runtime than O(n) if you only have one jar. To get a better runtime than O(n) you'd have to skip rungs to get some runtime less than O(n), but this means if you have one jar, and you skip rungs, you run the risk of breaking your jar and not knowing the highest rung it can be safely dropped at, so the algorithm would have no way of returning a specific rung, which would be an invalid solution.
I am stuck with the 2.8(b). How do we calculate the number of times we drop a jar? I am lost in the math.
ReplyDelete(And don't worry, I am done with the rest :)