as i ask question and answered by some Clever people at this topic:

Recurrence Relation Solving Problem

i try to learn new thing with new question very similar to get familiar with recurrence relation and order complexity:

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

$T(1) = 1$.

We want to calculate order of T. but without T(0) we cannot do it.

but if we have this equation:

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

$T(1) = 1$.

i think the order is O(2^n)? every one could add any detail or step by step solving?

  • 1
    $\begingroup$ One problem with the summation range including $k=n$ is that then it refers to $T(n-n)=T(0)$ but $T(0)$ is not given by the initial condition. Another problem is that the other term would be $T(n)$ which appears as the entire left side. Maybe the sum should go from $k=1$ to $k=n-1$ instead? [Also: I just looked at the linked question and it is identical, this is not just a similar problem.] $\endgroup$ – coffeemath May 31 '14 at 23:32
  • $\begingroup$ i edit the question... $\endgroup$ – user153695 Jun 1 '14 at 6:53
  • $\begingroup$ user153695-- I think you meant to have the upper limit of the sum to be $n-1$ but you did the edit wrong. I'll fix, and let me know if it looks like what you want, or it should be something else. $\endgroup$ – coffeemath Jun 1 '14 at 12:10
  • $\begingroup$ now it's ok. any idea foe solving? $\endgroup$ – user153695 Jun 1 '14 at 17:42
  • $\begingroup$ user153695 Though I think one of the answers in the linked page actually solves this, I've put an answer here which maybe explains more about the solving steps. $\endgroup$ – coffeemath Jun 1 '14 at 19:37

I'd like to note there are already at the linked question in this question two answers to this version of the question, and that I'm only putting another because maybe the OP can get something about motivation for steps.

First the recursion can be written more simply as $$T(n)=n+2\cdot\sum_{k=1}^{n-1}T(k),\tag{1}$$ since both inner sums in the original format end up adding $T(k)$ for all values of $k$ from $1$ to $n-1$ inclusive. Replacing $n$ by $n+1$ seems a good idea, since then subtraction will turn the initial $n$ into the simpler $1$. So $$T(n+1)=(n+1)+2\cdot \sum_{k=1}^n T(k).\tag{2}$$ Then after subtracting $(1)$ from $(2)$ we have $T(n+1)-T(n)=1+2T(n).$ More simply we have $T(n+1)=1+3T(n)$. If now only the extra $1$ wasn't there we could finish easily. One trick that is often used to "get rid of an added constant" like this is to form a new sequence based on the differences. Here if we define $S(n)=T(n+1)-T(n)$ then we arrive at $$S(n)=(1+3T(n))-(1+3T(n-1))=3T(n)-3T(n-1)=3S(n-1).$$ We then from $S(1)=T(2)-T(1)=4-1=3=3^1$ can show that $S(n)=3^n.$

Now we can put this into the definition of $S(n)=T(n+1)-T(n)$ and get $T(n+1)=T(n)+3^n,$ and since $T(1)=1=3^0$ we see that $T(n)$ amounts to summing up the powers of $3$ from $3^0$ up until $3^{n-1}$, which using the formula for geometric series sum gives the final form for $T(n)$ as $(3^n-1)/(3-1)=(3^n-1)/2.$ Note that this in any reasonable sense is "big O" of $3^n$ since it's asymptotic to half that.

  • $\begingroup$ it means the my question order is O(N^3)? or O(3^n)? or O(n^n)? $\endgroup$ – user153695 Jun 2 '14 at 10:00
  • $\begingroup$ It's the second one, if you want the smallest of these three. It isn't $O(n^3)$ because $3^n$ is larger. You could say it is $O(n^n)$ because $O(f(n))$ just means there is a positive constant $k$ so it is less than $kf(n)$ but usually one wants the smallest choice for $f(n)$ when using $O(f(n))$ notation, so in this case that would be $O(3^n)$ from the explicit form $T(n)=(3^n-1)/2.$ $\endgroup$ – coffeemath Jun 2 '14 at 12:00
  • $\begingroup$ you are so clever. thanks $\endgroup$ – user153695 Jun 2 '14 at 13:38

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.