1

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)

dreamcrash
  • 138
  • 1
    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.

     – Antonio Vargas Nov 28 '12 at 03:22

2 Answers2

3

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.

user1551
  • 139,064
  • thanks for replying I forgot an + 1 in the recurrence – dreamcrash Nov 28 '12 at 03:46
  • @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. – user1551 Nov 29 '12 at 11:25
1

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

Ross Millikan
  • 374,822