$\begingroup$

I have already looked at the answer here. I'm trying to understand how the poster got:

f(n) = O(1) = O(n^log_ba)

So far I have O(1) = T(n) - T(n/2). How is it that this became O(n^log_ba) ?

EDIT: After looking at the theorem, I'm also unsure how aT(n/b) = O(log_b n). Is there is a proof for the limit as x->inf for (n/(b^x)) that equals log_b n ?

$\endgroup$ 1

4 Answers

$\begingroup$

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$.

$\endgroup$ $\begingroup$

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)$.

$\endgroup$ $\begingroup$

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

$\endgroup$ 0 $\begingroup$

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,

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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