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?
$\begingroup$
$\endgroup$
-
$\begingroup$ Welcome to Computer Science! Let me direct you towards our reference questions which cover techniques that can be applied to solve your problem, in particular cs.stackexchange.com/q/2789/755. $\endgroup$ – D.W.♦ Dec 14 '16 at 9:52
$\begingroup$
$\endgroup$
A much better way is to use the master method :), check that out!
-
$\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$ – Logan Leland Dec 14 '16 at 1:11
-
$\begingroup$ Thx. I will check this document. BTW. My solution is good? $\endgroup$ – No Name Dec 14 '16 at 1:26
-
$\begingroup$
$\endgroup$
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.
