6 ms·

Given that is a theoretical question that you are attempting to fit into an actual algorithm to ostensibly solve a real problem, doesn't the actual performance

by Jd 14y ago

Given that is a theoretical question that you are attempting to fit into an actual algorithm to ostensibly solve a real problem, doesn't the actual performance of the algorithm matter? I can see that within the context of theory of computer science there may not be a difference between the speed of the two algorithms, since both are "asymptotically optimal" (a term I'm not sure I entirely grok), yet within virtually any defined set of random numbers less than infinity the algorithm I provided will perform substantially faster. I suppose I'm at a loss for words, since as a seasoned software developer without a deep background in theoretical computer science, it seems that I am being told to disregard my intuition based on experience in favor of a theoretical model that seems to ignore actual problem sets. Am I missing something?

bjourne 14y ago
I made a python script to time the different approaches: https://gist.github.com/3839551 https://gist.github.com/3839551 AFAICT, the parent and the interviewer is right because both methods run in roughly the same time because the time of the binary search is orders of magnitude greater than the upper bound finding part. I might have made one or more mistakes though.
- Jd 14y ago
  If I have time later today I'll extend your snippet, but my inclination is that the differences in speed become apparent only with very large numbers. I still suspect my algorithm is about 40-50% faster if you start with a googol.
  - sophotrope 14y ago
    It seems that the problem involves two parts: 1) To find an upper bound 2) Then divide the remaining region in halves until the number is found. The first observation that I have is that given that the secret number s is chosen, the first step can be completed arbitrarily quickly. One could use a function that rises arbitrarily fast. Imagine for example the function taking k to the Ackerman function A(2,2,k). That rises so fast it's incomprehensible, but really one could easily produce a function which rises faster still (the algorithm that picks s first!). The problem is, though, of how fast a fixed algorithm is for random s. If s is truly chosen at random from the positive integers, this leads to problems. Fix your putative algorithm. Suppose for the moment that it starts at 0 (it is not going to matter where it starts) What is the probability that the kth number that your function spits out is less than a random integer? 100% After all, how many integers are greater than any given integer? Therefore, no growth function is any better on average at finding the upper bound than any other. Therefore step 1) is an insoluble problem. The problem should have been specified in some other way in order for it to make sense. However, the second step involves log_2(n) time (in the worst-case-scenario and still O(log n) in general) where n is the upper bound --the output of step 1-- which means that the time to complete the algorithm is (Time of step 1 to find n) + O(log n). IF the problem made sense and it was the case that step 1) were soluble, then it would matter how fast step 1 is countered by the degree to which step 1 tends to overshoot the secret number --because overshooting by k has the penalty of log(k) extra operations. Is there are framework in which question 1 makes sense? It would make sense if there were a given probability distribution on the integers (a function on the positive integers whose sum over all integers = 1, for example choose the function f(n) = 6/(n^2 * pi^2)) A probability distribution gives you a way of answering the question: "what proportion of the positive integers are greater than k?"
    - mratzloff 14y ago
      Excellent response. I think the framing element that was missing is if the random numbers were truly random.
mratzloff 14y ago
This was my conclusion, that although the two approaches had the same average big O time, my intuition said it was somewhat faster to start from some number larger than 0. In retrospect, I might have mentioned this and then gave the interviewer's preferred answer in code, just to keep things simpler.
hexagonc 14y ago
My intuition says that they should almost always run at about the same time if you don't know anything about the distribution of guesses. Your algorithm has the advantage that it will find an upper bound for the number much faster than the interviewer's algorithm. HOWEVER, having found that upper bound, your algorithm will probably be much farther away from the actual number than the interviewer's, so you have to do that much more narrowing down. What it comes down to is being lucky that you're close to the number in your initial guess, otherwise, you're still talking logarithmic time to either find an upper bound or (in your case) lower bound for the number.

by Jd 14y ago

bjourne 14y ago

I made a python script to time the different approaches: https://gist.github.com/3839551 https://gist.github.com/3839551 AFAICT, the parent and the interviewer is right because both methods run in roughly the same time because the time of the binary search is orders of magnitude greater than the upper bound finding part. I might have made one or more mistakes though.

Jd 14y ago
If I have time later today I'll extend your snippet, but my inclination is that the differences in speed become apparent only with very large numbers. I still suspect my algorithm is about 40-50% faster if you start with a googol.
- sophotrope 14y ago
  It seems that the problem involves two parts: 1) To find an upper bound 2) Then divide the remaining region in halves until the number is found. The first observation that I have is that given that the secret number s is chosen, the first step can be completed arbitrarily quickly. One could use a function that rises arbitrarily fast. Imagine for example the function taking k to the Ackerman function A(2,2,k). That rises so fast it's incomprehensible, but really one could easily produce a function which rises faster still (the algorithm that picks s first!). The problem is, though, of how fast a fixed algorithm is for random s. If s is truly chosen at random from the positive integers, this leads to problems. Fix your putative algorithm. Suppose for the moment that it starts at 0 (it is not going to matter where it starts) What is the probability that the kth number that your function spits out is less than a random integer? 100% After all, how many integers are greater than any given integer? Therefore, no growth function is any better on average at finding the upper bound than any other. Therefore step 1) is an insoluble problem. The problem should have been specified in some other way in order for it to make sense. However, the second step involves log_2(n) time (in the worst-case-scenario and still O(log n) in general) where n is the upper bound --the output of step 1-- which means that the time to complete the algorithm is (Time of step 1 to find n) + O(log n). IF the problem made sense and it was the case that step 1) were soluble, then it would matter how fast step 1 is countered by the degree to which step 1 tends to overshoot the secret number --because overshooting by k has the penalty of log(k) extra operations. Is there are framework in which question 1 makes sense? It would make sense if there were a given probability distribution on the integers (a function on the positive integers whose sum over all integers = 1, for example choose the function f(n) = 6/(n^2 * pi^2)) A probability distribution gives you a way of answering the question: "what proportion of the positive integers are greater than k?"
  - mratzloff 14y ago
    Excellent response. I think the framing element that was missing is if the random numbers were truly random.

mratzloff 14y ago

This was my conclusion, that although the two approaches had the same average big O time, my intuition said it was somewhat faster to start from some number larger than 0. In retrospect, I might have mentioned this and then gave the interviewer's preferred answer in code, just to keep things simpler.

hexagonc 14y ago

My intuition says that they should almost always run at about the same time if you don't know anything about the distribution of guesses. Your algorithm has the advantage that it will find an upper bound for the number much faster than the interviewer's algorithm. HOWEVER, having found that upper bound, your algorithm will probably be much farther away from the actual number than the interviewer's, so you have to do that much more narrowing down. What it comes down to is being lucky that you're close to the number in your initial guess, otherwise, you're still talking logarithmic time to either find an upper bound or (in your case) lower bound for the number.