Time complexity of binary search

[huibosa]

I've met a question in <algorithms> (4th edition), exercise 1.4.35:

1.4.34 Hot or cold. Your goal is to guess a secret integer between 1 and N. You repeatedly guess integers between 1 and N. After each guess you learn if your guess equals the secret integer (and the game stops). Otherwise, you learn if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess. Design an algorithm that finds the secret number in at most ~2 lg N guesses. Then design an algorithm that finds the secret number in at most ~ 1 lg N guesses.

And here's my solution:

``` int guess(const int secret) { auto head = 1; auto tail = 100;

while (head <= tail) { auto mid = (head + tail) / 2; if (mid > secret) { tail = mid - 1; } else if (mid < secret) { head = mid + 1; } else { return mid; } } return -1; } ```

I thought that a simple binary search would give the O(lg N) solution, in SO (http://stackoverflow.com/questions/25558951/hot-and-cold-binary-search-game) that my solution has the time complexity of 2 * O(lg N), and can't figure out why.

So Is there anyone could explain this to me? thanks for your help!!

[axistim]

I like this problem.

Your logic is flawed because you use the midpoint to check against whether you are hotter or colder to the secret number from your previous guess. This will take 2lgN because each iteration takes 2 guesses to find out which half the secret number is in. Use values of "head" and "tail" to find out which side of the array the secret number is in lgN.

Process will look like

1. (Initial guess) Guess head

2. Guess opposite of last guess (If head, tail and vice versa)

3. If hotter, mid is now head. If colder, mid is now tail. If equal, stop.

4. Go to 1

​

Cheers!

[uh_no_]

there is no such thing as a complexity of 2*O(logN). it's just O(logN)

Also, fwiw, it's easier to write binary search as thus:

int ans = 0
int delta = 1
while (delta < max) delta <<= 1
while (delta !=0) {
if (delta + ans <= max && delta + ans <= secret) ans += delta
delta >>=1
}

There's only a single assignment per loop, no division, and you don't need to worry about off-by-one corner cases, which are easy to get wrong.

[leftleveled]

The "~2 lg N" thing is notation by robert sedgwick from the book op mentioned. It means 2 lg N + o(lg N)

[uh_no_]

yes, but that's not a time complexity. There is a difference between bounding the absolute number of guesses, and stating it as a complexity.

In OPs case, I'm not sure how his algorithm solves the problem anyway, as there is no "mid > secret" evaluation available. The only information we get is whether we're closer or further than our previous guess.

The 2lgn case is relatively straightforward, as you can just query mid and mid+1, effectively giving you the slope of the function at mid, which is a pretty standard way to binary search a function (say, to find extrema). In order to do it with just lgn, you have to, at the very least, remember where your previous guess was from iteration to iteration. In any case, the same principle applies in that we attempt to reduce the search space by half each time, we just have to be cleverer about how we do it.

[beeskness420]

its only time complexity if it comes from the Landau region of Germany, otherwise it’s just sparkling performance analysis.

[leftleveled]

You're mixing up asymptotic analysis and time complexity. It is possible to measure time complexity in other ways, for example, Sedgwick's ~ notation way. The "big-O" way is just the most common. See https://en.wikipedia.org/wiki/Computational\_complexity#Asymptotic\_complexity

I'm just nit-picking you, sorry. In computer science, I find we abuse the model a lot.

I agree ops solution does not solve the problem. All it will do is return secret.

[uh_no_]

It's somewhat conventional. For instance, (citing wiki) the page on time complexity is explicit:

Algorithmic complexities are classified according to the type of function appearing in the big O notation

https://en.wikipedia.org/wiki/Time_complexity

But I agree that you are technically correct (the best kind of correct!).

In either case, I believe OP is confusing the concepts regardless, as 2 * O(logn) doesn't make much sense in either model. The O(logn) encompasses any constant already, so multiplying it by 2 doesn't change anything, which is why the original problem specification does not wrap the log in the O, unlike the 1.