1

I know that recursive equation of this algo is

$T\left ( n \right )=2T\left ( \frac{n}{2} \right )+2 $

Given that $T\left ( 1 \right )=0,T\left ( 2 \right )=1 $

and its solution is also given here, ijust want to clear my doubt where i am stuck at.. I solved this eqtn as--:

$\Rightarrow T\left ( n \right )=2\left ( 2*T\left ( \frac{n}{4} \right )+2 \right )+2 $

$\Rightarrow T\left ( n \right )=2^{2}+T\left ( \frac{n}{2^{2}} \right )+2^{2}+2^{1}$

$\vdots$

$\Rightarrow T\left ( n \right )=2^{k}*T\left ( \frac{n}{2^{k}} \right )+2^{k}+\cdots 2^{2}+2^{1}$

Taking $T\left ( 1 \right )=0 $

$\frac{n}{2^{k}}=1 \Rightarrow k=\log_{2}n $

And our equation becomes

$2^{k}+2^{k-1}+\cdots 2^{2}+2^{1} = \frac{2*\left ( 1-2^{k} \right )}{1-2}=2n-2 ,\left \{ 2^{k}=2^{log_{2}n}=n\right \} $

But answer is $\frac{3*n}{2}-2$..please correct me in this equation.

Community
  • 1
sourav_anand
  • 551

2 Answers2

1

You can check as followed that your solution fits the recurrence like this:
$T(1)=2\cdot 1-2=0$
$T(n) = 2n-2 = 2(2\frac{n}{2}-2) +2 = 2\cdot T(\frac{n}{2}) + 2$
Similarly you can check that the answer you have been given fits:
$T(2)=1$
$T(n) = 2\cdot T(\frac{n}{2}) + 2$
How to reconcile these 2 facts? Well the 2 base-cases aren't compatible. Try:
$T(2) = 2\cdot T(\frac{2}{2}) + 2 = 2\cdot T(1) + 2$
If we assume $T(1)=0$, we get:
$T(2) = 2\cdot 0 + 2 = 2$
If we assume $T(2)=1$, we get:
$1=T(2) = 2\cdot T(1) + 2 \implies T(1)=-\frac{1}{2}$

So the 2 different base cases give 2 different solutions for the recurrence. If you want the other solution, use the other base-case in your derivation.

edit: to see what happens, we use:
$\frac{n}{2^k}=2\implies k = (\log_2{n})-1$
And the equation becomes:
$2^{k}\cdot 1+2^{k}+2^{k-1}+\cdots 2^{2}+2^{1} =2^{k}+ \frac{2*\left ( 1-2^{k} \right )}{1-2}=\frac{n}{2}+2\frac{n}{2}-2=\frac{3\cdot n}{2}-2 ,\left \{ 2^{k}=2^{(log_{2}n)-1}=\frac{n}{2}\right \} $

dimpol
  • 312
  • 1
  • 2
  • 8
  • but it is given $\frac {3*n}{2} -2$ see the link http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/ and http://math.stackexchange.com/questions/54019/recurrence-relation-for-max-and-min-of-a-sequence?noredirect=1&lq=1 – sourav_anand Nov 02 '16 at 16:31
  • See my edit, if you use the other base case in your last few steps, you get the answer you want. – dimpol Nov 02 '16 at 16:39
  • i answered my question before i see your edit ..thankx !! but still stuck that changing base case will change the answer ..it is really dangerous ! – sourav_anand Nov 02 '16 at 16:51
1

Changing my base case from $T\left ( 1 \right )=0$ to $T\left ( 2 \right )=1 $ .my equation looks like

$\Rightarrow T\left ( n \right )=2^{k}*T\left ( \frac{n}{2^{k}} \right )+2^{k}+\cdots 2^{2}+2^{1}$

Taking $T\left ( 2 \right )=1 $

$\frac{n}{2^{k}}=2 \Rightarrow k=\log_{2}\frac{n}{2} $

And our equation becomes

$T\left(n \right)=2^{k}+2^{k}+2^{k-1}+\cdots 2^{2}+2^{1}$

$2^{k}=\frac{n}{2}$ $T\left(n \right)=2^{k}+\sum_{j=1}^{j=k}2^{j}$

$T\left(n \right)=2^{k}+2*\frac{2^{k}-1}{2-1}$

$T\left(n \right)=\frac{n}{2} +2*\left(\frac{n}{2} -1 \right) $

$T\left(n \right)=\frac{3n}{2}-2$

sourav_anand
  • 551