Solve Recurrence Relation for Maximum and Minimum in an Array.

Question

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.

Answer 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$

Answer 2

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 \} $