Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
The online book mentioned here does not use the same approach but reaches the conclusion in a step by step way showing that binary search's worst-case number of comparisons is $2\log_{2} (n+1)$. here is the link if you are interested: books.google.ca/… –  Emmad Kareem Sep 6 '12 at 0:21

4 Answers 4

up vote 0 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.