So this is probably a basic and slightly stupid question. So.....for a binary search to find a number it takes at most 2Log(n)+1 steps (or Log(2N) questions.

Im not a math major or anything, but simply a CS grad trying to remember back from college 5 years ago (Im trying to re-pick back up CS theory).

I guess I don't understand how we come to this? What I suppose "branch" of mathematics is this? I feel like although I passed my calc classes/ cs/math classes.....I prolly didn't retain much (due to rushing to get programming assignments done). Is this all discrete math where this is learned?


If you write $T(n)$ for the number of comparisons needed for finding a fixed element $x$ in a sorted list of $n$ elements (in the worst case), you get $T(0)=0$, $T(1)=1$; and you also can get a recurrence relation of the form $$T(n)=T\left(\left\lceil \frac{n}{2}\right\rceil\right)+1$$ (can you see why? The $+1$ is the comparison of $x$ with the median element to decide on which of the two halves of the list to recurse). I recommend solving it without the ceilings/floors at first, e.g. assuming $n$ is a power of $2$ -- the general case is a bit messier, but exactly the same idea.

Incidentally: (assuming as usual in CS that the logarithm is in base 2) $\log(2n) = \log 2 + \log n = \log n +1 \neq 2\log n +1 = \log(2n^2)$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy