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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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|cite|improve this question

marked as duplicate by Live Forever, dustin, amWhy, kingW3, Johanna Feb 22 '15 at 2:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
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
up vote 1 down vote accepted



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





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

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



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

share|cite|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
@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|cite|improve this answer

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