Hello and thanks for taking the time to answer my question.

The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I prove that this is correct?

I would really appreciate your reasoning behind the concepts as opposed to just churning out a solution.

Thank you very much!

  • $\begingroup$ Are you seeking to merely prove the claim, or are you asking how you would discover it if it weren't given to you? What happens, incidentally, when you try the method of substitution or induction? $\endgroup$ – user14972 Jan 15 '13 at 16:35

The most basic method is to expand the formula. It rarely works, but it is simple enough that is worth checking before proceeding to more complicated stuff.

\begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) + n \\ &= T(0) + \frac{n(n+1)}{2} = O(n^2) \end{align}


EDIT: Added missing $T(0) = O(1)$ term (thanks to Hurkyl).

| cite | improve this answer | |
  • 2
    $\begingroup$ You mean $T(0) + n(n+1)/2$ $\endgroup$ – user14972 Jan 15 '13 at 16:36
  • $\begingroup$ This is great thanks dtldarek! I will accept your answer as correct as soon as the minimum required time elapses! How would you determine the lower bound for the same equation? $\endgroup$ – Peter Jan 15 '13 at 16:40
  • $\begingroup$ @Peter This is actually set of equalities, so those work both ways. In fact $T(0) + \frac{n(n+1)}{2} = \Theta(n^2)$. $\endgroup$ – dtldarek Jan 15 '13 at 16:42
  • $\begingroup$ oh okay.. I asked the second question in the comment because as far as I understand it O denotes the upper bound which means that T(n) <= O(n^2) and for Omega it is the opposite. Does this mean that for T(n) = (n-1) + n Big O and Omega are n^2 aswell? $\endgroup$ – Peter Jan 15 '13 at 16:46
  • 1
    $\begingroup$ @evinda That depends on the starting conditions, which in the original post were not given. On the other hand, it doesn't matter, as both $T(0)$ and $T(1)$ are constant. In other words, pick the one that is more convenient for you. $\endgroup$ – dtldarek Mar 7 '15 at 23:03

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.