-1
$\begingroup$

Can anyone help me in solving this complex recurrence in detail?

$T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $

$T(1) = 1$.

We want to calculate order of T.

I'm confused by using recursion tree and some maths induction.

$\endgroup$
  • 1
    $\begingroup$ Here's a MathJax tutorial :) $\endgroup$ – Shaun May 27 '14 at 16:43
  • 1
    $\begingroup$ Should $k$ range from $1$ to $n-1$ instead of $n$? $\endgroup$ – fahrbach May 27 '14 at 16:49
  • 1
    $\begingroup$ I put in the $\LaTeX$ for you. Please note that $k \neq K$ and $n \neq N$ but I left them as they were. I presume you meant them to be the same. Also please check the upper limit of the sum. $\endgroup$ – Ross Millikan May 27 '14 at 16:50
  • $\begingroup$ i correct it and wait for answersss $\endgroup$ – user153695 May 27 '14 at 16:55
  • 1
    $\begingroup$ Putting $k-1$ under the summation sign does not indicate the variable you are summing over. Having $k=$ something will tell that and show what to start at. That is why I put in $k=1$ What should it start at? $\endgroup$ – Ross Millikan May 27 '14 at 17:37
1
$\begingroup$

Starting with: $$ T(n) = n + \sum_{k=1}^{n-1} \left[T(n-k) + T(k)\right] $$ The two terms in the square braces are the same; one is counting down and the other counting up, so: $$ T(n) = n + 2\times \sum_{k=1}^{n-1} T(k) $$ To find the order of $T$, we need to compare $T(n)$ to $T(n-1)$. $$ T(n-1) = (n-1) + 2\times \sum_{k=1}^{n-2} T(k) $$ So we rearrange terms in the definition of $T(n)$: $$ \begin{align} T(n) &= [(n-1) + 1] + 2\times \left[ \left(\sum_{k=1}^{n-2} T(k)\right) + T(n-1)\right]\\ &= 1 + \left[(n-1) + 2\times \left(\sum_{k=1}^{n-2} T(k)\right)\right] + 2\times T(n-1)\\ &=1 + T(n-1) + 2\times T(n-1)\\ &= 3\times T(n-1) + 1 \end{align} $$

Thus, $T(n)$ is $O(3^n)$. Given that $T(1) = 1$, we see $T(n) = 3^n/2-1/2$.

$\endgroup$
  • $\begingroup$ i think it's wrong and answer maybe is O(n lg n)... what's your idea? $\endgroup$ – user153695 May 27 '14 at 20:19
  • $\begingroup$ Why do you think it's wrong? Do you see something wrong in my proof? Do you know of a value were $T(n) \neq 3^n/2-1/2$? Or do I have the wrong initial recursive function definition? $\endgroup$ – user3294068 May 27 '14 at 21:21
  • $\begingroup$ Even assuming that you meant to write k=1 as the bottom summation limit, you're still going to have problems with n as the upper limit. Try it for n=2 to see what happens. (A reasonable problem statement would have n−1 as the upper limit.) $\endgroup$ – user153695 May 29 '14 at 4:53
1
$\begingroup$

Use generating functions. Define $g(z) = \sum_{n \ge 0} T(n + 1) z^n$, write yout recurrence as: $$ T(n + 2)= n + 2 + 2 \sum_{1 \le k \le n + 1} T(n) $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums: $$ \frac{g(z) - T(1)}{z} + z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} + \frac{2}{1 - z} + 2 \frac{g(z)}{1 - z} $$ go get, written in partial fractions: $$ g(z) = \frac{3}{2} \cdot \frac{1}{1 - 3 z} - \frac{1}{2} \cdot \frac{1}{1 - 2 z} $$ Thus: $$ T(n) = \frac{3^n}{2} - 2^{n - 2} $$

$\endgroup$
  • $\begingroup$ it's so difficult :) you are so clever for nice solution. it means the order is O(n^n) or O(3^n)? $\endgroup$ – user153695 May 29 '14 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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