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)

  • 2
    No, it doesn't. What's the solution you got? Did you try it? Does it work?2012-11-28
  • 0
    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.2012-11-28
  • 0
    I am not being mean ; I am asking the questions you should ask yourself to convince yourself that you are right. In other words I'm telling you how to answer yourself in the future. It might sound mean, but it is exactly what you need to hear ; put your feelings aside and give it some thought. =)2012-11-28
  • 0
    By the way ; I know you tried and it's a good thing you did. I was asking if you tried the solution that you had, i.e. if you had tried to put numbers in it to see if it works.2012-11-28
  • 0
    @PatrickDaSilva, Yes, and It does not make sense at the time, thats why I put here the "this makes any sense" it just introductory "manbo jumbo" xD. I really do not need the right solution I just need the O(..). I have the feeling that it is O(n), but I don't really know how to get there.2012-11-28
  • 1
    Hmm, I don't understand the recurrence relation itself. What is meant by $T(n/2)$ when $n$ is odd?2012-11-28
  • 0
    @user1551 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)2012-11-28
  • 0
    @dreamcrash : That is very, very important to know.2012-11-28
  • 1
    @PatrickDaSilva I should had added to the question.2012-11-28
  • 0
    What are your initial conditions?2012-11-28
  • 0
    The recurrence stops when n = 12012-11-28
  • 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)$](http://i.imgur.com/47GuX.png), it looks like $T(n)$ has superlinear growth.2012-11-28
  • 0
    @AntonioVargas I forgot that it had 1 in the recurrence. Portugues?2012-11-28
  • 0
    Sorry, only English :)2012-11-28

2 Answers 2

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

  • 0
    This maybe a silly question but \phi will have a value between 1 < \phi <2 ?2012-12-02
  • 0
    @dreamcrash: $\phi = \frac 12(1+\sqrt 5)$ which is in that interval2012-12-02
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.

  • 0
    thanks for replying I forgot an + 1 in the recurrence2012-11-28
  • 0
    @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.2012-11-29