1
$\begingroup$

I am try to find the solution to the recurrence T(n) = T (n-1) + T(n/2) + 1

Whats I have done:

T(n) = 2T(n-1 + n/2) + 1
T(n) = 2T(2n/2 - 2/2 + n/2) +1
T(n) = 2 T((3n - 1)/2) +1

if U(X) = T(x/3 + 1) then:

U(X) = 2U(x/2)
U(X) = x

T(n) = 3(N  - 1) + 1

This makes any sense ?

Edit: The context is computer science, so when you divide n/2 and n odd you get the next inferior natural number (e.g 1/2 -> 0)

$\endgroup$
  • 2
    $\begingroup$ No, it doesn't. What's the solution you got? Did you try it? Does it work? $\endgroup$ – Patrick Da Silva Nov 28 '12 at 0:59
  • $\begingroup$ I try on T(4) it gives me 9 I think it suppose to be 8. Yes I did try, not every one is an expert in mathematic. $\endgroup$ – dreamcrash Nov 28 '12 at 1:07
  • 1
    $\begingroup$ Hmm, I don't understand the recurrence relation itself. What is meant by $T(n/2)$ when $n$ is odd? $\endgroup$ – user1551 Nov 28 '12 at 1:21
  • 1
    $\begingroup$ @PatrickDaSilva I should had added to the question. $\endgroup$ – dreamcrash Nov 28 '12 at 1:27
  • 1
    $\begingroup$ A couple simple estimates... If $T(1) \geq 0$ then $T(n) \geq 0$ for all $n$ and thus $T(n) \geq T(n-1)$ for all $n$. This gives $$T(n) \geq 2T(\lfloor n/2 \rfloor) \geq 2^{\lfloor \log_2 n \rfloor} T(1)$$ and $$T(n) \leq 2 T(n-1) \leq 2^{n-1} T(1).$$ Based on the plot of the values of $T(n)$, it looks like $T(n)$ has superlinear growth. $\endgroup$ – Antonio Vargas Nov 28 '12 at 3:22
1
$\begingroup$

This series is shown in OEIS. It clearly grows more slowly than the Fibonacci numbers, as you increment by smaller values. This shows $T(n) \in o(\phi ^n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This maybe a silly question but \phi will have a value between 1 < \phi <2 ? $\endgroup$ – dreamcrash Dec 2 '12 at 3:35
  • $\begingroup$ @dreamcrash: $\phi = \frac 12(1+\sqrt 5)$ which is in that interval $\endgroup$ – Ross Millikan Dec 2 '12 at 3:37
3
$\begingroup$

Your first line, $$T(n) = 2T(n-1 + n/2),$$ is already nonsensical. The problems are twofold. First, $T$ is not guaranteed to be additive, so $T(n-1)+T(n/2)$ (the RHS of the original recurrence relation) is not necessarily equal to $T(n-1 + n/2)$. Second, even if $T$ is additive, what you get should be $T(n) = T(n-1) + T(n/2) = T(n-1 + n/2)$, but for some curious reason, you further throw in a multiplicative factor of $2$ to get $T(n) = 2T(n-1 + n/2)$.

At any rate, the sequence generated by the recurrence relation $T(n)=T(n-1)+T(\lfloor n/2\rfloor)$ has been indexed as A033485 in OEIS. According to OEIS, when $T(1)=1$, the sequence "gives the number of partitions of 2n into 'strongly decreasing' parts". Apparently no closed form solution for $T(n)$ is known.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for replying I forgot an + 1 in the recurrence $\endgroup$ – dreamcrash Nov 28 '12 at 3:46
  • $\begingroup$ @dreamcrash: If the recurrence relation without the trailing 1 has no known solution, there is little chance that, with the trailing 1, the relation would have a closed form solution. $\endgroup$ – user1551 Nov 29 '12 at 11:25

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.