Solve Recurrence Relation for Maximum and Minimum in an Array. 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.
 A: 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 \} $
A: 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$
