1
$\begingroup$

I tried to calculate the worst case of binary search (not binary search tree). My calculations: $$T(n) = T(\frac{n}{2}) + 1$$ $$T(n) = T\left(\frac{n}{4}\right) + (1+1) = T\left(\frac{n}{8}\right) + (1+1+1) = ... = 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
$\begingroup$

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

$\endgroup$
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, privacy policy and cookie policy

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