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?
$\begingroup$
$\endgroup$
1
-
$\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, 2016 at 9:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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$ Dec 14, 2016 at 1:11
-
$\begingroup$ Thx. I will check this document. BTW. My solution is good? $\endgroup$– No NameDec 14, 2016 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.
