How to prove $O(\log n)$ is true for a binary search algorithm? I have already looked at the answer here. I'm trying to understand how the poster got:

f(n) = O(1) = O(nlogba)

So far I have O(1) = T(n) - T(n/2). How is it that this became O(nlogba) ?
EDIT: After looking at the theorem, I'm also unsure how aT(n/b) = O(logb n). Is there is a proof for the limit as x->inf for (n/(b^x)) that equals logb n ? 
 A: To do the specific case without the Master Theorem, the recurrence is $T(n)=T(n/2)+1$ because with one compare we can cut in half the number of places something can be.  For simplicity, assume $n$ is a power of $2$.  Then $T(1)=0$, because with one item we can find the right one  without a compare.  Similarly $T(2)=1$ because we have just one compare to do.  Both of these satisfy $T(n)=\log_2 n$-the base case for our induction.  Now to proceed by induction, assume $T(2^n)=n$.  Then $T(2^{n+1})=T(2^n)+1=n+1=\log_2 (2^{n+1})$ and we have established it for all powers of $2$.  The first equality used the recurrence, the second used the inductive assumption, and the third used the definition of $\log_2$.
A: The recurrence for binary search is $T(n)=T(n/2) + O(1)$. The general form for the Master Theorem is $T(n)=aT(n/b) + f(n)$. We take $a=1$, $b=2$ and $f(n)=c$, where $c$ is a constant. The key quantity is $\log_b a$, which in this case is $\log_2 1=0$. 
If you look at the Wikipedia entry (through the link you posted) you will see that there are 3 main cases for the Master Theorem. Here we are in Case 2 since by taking $k=0$ we find that $n^{\log_b a}(\log n)^k=(n^0)(\log n)^0=1$; therefore $f(n)=c=\Theta(n^{\log_b a}\log^k n)$.
From Case 2 of the Master Theorem we know that $T(n)=\Theta(n^{\log_b a}(\log n)^{k+1}$ which in this case yields $T(n)=\Theta(n^0(\log n)^1)=\Theta(\log n)$.
A: It's because in the answer you referenced to, $a=1$ and $b=2$ so $\log_ba=0$. This is done to match the form of $f$ in the Master Theorem
A: refering to the final answer 
$T(n) = O(n^{\log_b a} \log_{2} n)) = O(\log_{2} n)$
The answer is very simple because the $O(\log_{2} n)$ is much more rapid than $O(n^{\log_b a}$ we igonore the other parametr,
