2
$\begingroup$

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 ?

  • 0
    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: http://books.google.ca/books?id=YhD9Zc5tp7wC&pg=PA282&lpg=PA282&dq=deriving+order+binary+search&source=bl&ots=z3tTCdSUYc&sig=68h-QnDUczu3_TynRCa2Mcda29E&hl=en&sa=X&ei=5upHUMTsIIeg4gSw2YCIBA&ved=0CC0Q6AEwAA#v=onepage&q=deriving%20order%20binary%20search&f=false2012-09-06

4 Answers 4

3

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

0

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

0

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

0

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,