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.

  • $\begingroup$ 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)$. $\endgroup$ – cr001 Sep 18 '17 at 22:03
  • $\begingroup$ Can you clarify your reasoning for the quadratic relationship? $\endgroup$ – jenkelblankel Sep 18 '17 at 22:16
  • $\begingroup$ 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$. $\endgroup$ – cr001 Sep 18 '17 at 22:20
  • $\begingroup$ Ok I see that now. Thank you. $\endgroup$ – 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)$

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

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.