# 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 ?

-

– Emmad Kareem Sep 6 '12 at 0:21

## 4 Answers

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

-

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

-

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

-

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,

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 31, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9472498893737793, "perplexity_flag": "head"}