Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following recurrence relation $$T(n) = T(n-1) + T(n/2) + n .$$ I know that I cannot use Master's theorem here and by intuition I can see the relation will be of order $O(n^2)$.

But how to solve it, I have tried iterative method which was futile. Please help.

share|improve this question
2  
Is n^2 a mistyped n-2? Otherwise, since $n^2\geq n$, how can you say that this is a recurrence relation? –  AndreasT Mar 30 '13 at 10:51
    
@AndreasT Sorry its n/2 not n^2. –  Maverick Snyder Mar 30 '13 at 11:05
2  
Then what about odd $n$? –  AndreasT Mar 30 '13 at 12:33
    
@AndreasT Does it really matter, if the question would have been T(n) = T(n/2) + n then I would have used iterative method and get T(n) = n + n/2 +n/4 . . . n/n and I would eventually get T(n) = $n(1− {1/2}^{log_2n+1})/(1-1/2)$ = 2n-1, which takes care of odd and even numbers. –  Maverick Snyder Mar 30 '13 at 16:19

2 Answers 2

up vote 1 down vote accepted

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

$T(n)-T(n-1)-T\left(\dfrac{n}{2}\right)=n$

Getting the particular solution part is very easy.

Let $T_p(n)=An+B$ ,

Then $An+B-(A(n-1)+B)-\left(\dfrac{An}{2}+B\right)\equiv n$

$-\dfrac{An}{2}+A-B\equiv n$

$\therefore\begin{cases}-\dfrac{A}{2}=1\\A-B=0\end{cases}$

$\begin{cases}A=-2\\B=-2\end{cases}$

$\therefore T_p(n)=-2n-2$

But getting the complementary solution part is quite difficult.

Since we should handle the equation $T_c(n)-T_c(n-1)-T_c\left(\dfrac{n}{2}\right)=0$ .

Let $T_c(n)=\int_0^\infty2^{nt}K(t)~dt$ ,

Then $\int_0^\infty2^{nt}K(t)~dt-\int_0^\infty2^{(n-1)t}K(t)~dt-\int_0^\infty2^{\frac{nt}{2}}K(t)~dt=0$

$\int_0^\infty2^{-nt}K(t)~dt-\int_0^\infty2^{nt}2^{-t}K(t)~dt-\int_0^\infty2^{nt}K(2t)~d(2t)=0$

$\int_0^\infty((1-2^{-t})K(t)-2K(2t))2^{nt}~dt=0$

$\therefore(1-2^{-t})K(t)-2K(2t)=0$

$K(2t)=\dfrac{1-2^{-t}}{2}K(t)$

Let $\begin{cases}t=2^u\\K(t)=F(u)\end{cases}$ ,

Then $F(u+1)=\dfrac{1-2^{-2^u}}{2}F(u)$

$F(u)=\dfrac{\prod\limits_{s=0}^\infty(1-2^{-2^u2^s})}{2^u}$

$K(t)=\dfrac{\prod\limits_{s=0}^\infty(1-2^{-t2^s})}{t}$

$\therefore T_c(n)=C\int_0^\infty\dfrac{2^{nt}\prod\limits_{s=0}^\infty(1-2^{-t2^s})}{t}dt$

share|improve this answer
    
"Getting the particular solution part is very easy." "But getting the particular solution part is very difficult." –  Steven-Owen Apr 24 '13 at 2:49
1  
@ricky: Sorry about the typo. I have been modified. –  doraemonpaul Apr 24 '13 at 2:58
    
It's a fantastic answer. –  Steven-Owen Apr 24 '13 at 3:03

If $T(n) = T(n-1) + T(n/2) + n$, it looks to me that $T(n)$ grows quite quickly.

Suppose that $T$ is smooth and $T(n) \approx a n^b + O(n^{b-1})$. Then $T(n-1) = a(n-1)^b + O((n-1)^{b-1}) = an^b -abn^{b-1} + O(n^{b-1}) = an^b + O(n^{b-1}) $ so $an^b+O(n^{b-1}) =an^b + O(n^{b-1})+a(n/2)^b + O(n/2)^{b-1}+n $ or $a(n/2)^b=O(n^{b-1}) $ which is never true. So, in this case, $T(n)-T(n-1)$ is smaller than $T(n/2)$.

Arguing the other way, if $T$ grows exponentially, $T(n) \approx a b^n$, then $T(n)-T(n-1) \approx ab^n - ab^{n-1} =a(b-1)b^{n-1}$ and this is larger than $T(n/2)$.

So, unless I have made a mistake (p > .37), $T$ has a growth between powers and exponential. Maybe something like $b^{n^c}$ where $0 < c < 1$ or $b^{n/\ln n}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.