I need to give a tight asymptotic bound to this recurrence relation.

The recurrence is:

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

I realize that this is fairly simple. I am asking where to start? If I should use the substitution method, what would be a good guess? I do not need help solving it, what I need is just the start. That is where I am confused.

• You should immediately realize this is a quadratic relationship because as $n$ increases $2n-1$ also increases at the same rate and then use induction to prove both upper and lower boundness for $\theta(n^2)$. – cr001 Sep 18 '17 at 22:03
• Can you clarify your reasoning for the quadratic relationship? – jenkelblankel Sep 18 '17 at 22:16
• Think in terms of actual coding: It is like a recursion: in every iteration of the function, we call itself once and do $2n-1$ things. Because it calls itself only once there is no branching in the recursion tree. Hence it is essentially a for-loop with $n$ iterations, each iteration doing (2i-1) things where $i=1..n$. – cr001 Sep 18 '17 at 22:20
• Ok I see that now. Thank you. – jenkelblankel Sep 18 '17 at 22:38

### 1. Solve linear equation

Solve homogeneous equation $$T(n)=T(n-1)$$ thus $$T(n)=cst$$.

Find a particular solution : $$T(n)=(an^2+bn+c)(1^n)\quad$$ (generally one more degree than RHS)

$$an^2+bn+c=a(n-1)^2+b(n-1)+c+2n-1\iff 0=-2an+a-b+2n-1\iff 2n(1-a)+(a-b-1)=0\iff a=1,\ b=0$$

Final solution $$T(n)=n^2+c$$

### 2. Telescoping method

$$T(n)-T(0)=\sum\limits_{k=1}^n \left(T(k)-T(k-1)\right)=\sum\limits_{k=1}^n (2k-1)=n(n+1)-n=n^2$$

Thus $$T(n)=n^2+T(0)$$

• Awesome. Thanks a ton. – jenkelblankel Sep 18 '17 at 23:19