1
$\begingroup$

I tried to calculate the worst case of binary search (not binary search tree). My calculations: $$T(n) = T\left(\frac{n}{2}\right) + 1$$ $$T(n) = T\left(\frac{n}{4}\right) + (1+1) = T\left(\frac{n}{8}\right) + (1+1+1) = {\dots} = T\left(\frac{n}{2^{k}}\right)+(1\cdot k) $$ $$T(n)=T(1) + (1\cdot k) = c_{1} + (1\cdot k) = c_{1} + log_{2}n = c_{1}+\frac{log(n)}{log(2)} $$ Finally the complexity should be $$O(log(n)) $$ Is this a good way to prove the worst case complexity of binary search algorithm? Make I mistakes?

$\endgroup$
1

2 Answers 2

1
$\begingroup$

A much better way is to use the master method :), check that out!

$\endgroup$
3
  • $\begingroup$ Here is a useful document when working on things like this: it includes the master method. google.com/url?sa=t&source=web&rct=j&url=http://… $\endgroup$ Dec 14, 2016 at 1:11
  • $\begingroup$ Thx. I will check this document. BTW. My solution is good? $\endgroup$
    – No Name
    Dec 14, 2016 at 1:26
  • $\begingroup$ This solution is okay $\endgroup$ Dec 14, 2016 at 1:27
2
$\begingroup$

That's a way to do it. Sometimes it's easier to go the other way round: What is the size of the largest array where binary search will locate an item or determine it's not there, using k comparisons? And it turns out that the largest array has size $2^k - 1$. And then you reverse this.

Understanding the master method is very useful if you have to pass a test that tests whether you understand the master method. But be prepared to have more practical problem where the only method that works is the "turn on your brain" method. A simple example is the Greatest Common Divisor algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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