# Proof by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$

How to prove by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$?

I've tried the following and got stuck

\begin{align} T(n) &= T(n - 1) + \Theta(n) \\ &= d(n - 1)^2 + cn \\ &= d(n^2 - 2n + 1) + cn \\ &= dn^2 - 2dn + d + cn .... \\ \end{align} Any ideas?

Thanks for your time and effort!

-
+1 to cancel the downvote. IMO, a question with a partial solution in the right direction isn't worth a downvote. – Rick Decker Jan 22 '13 at 2:56
Okay, Peter, it's time to take Steven's advice and upvote and/or accept one or both of the answers (of course, you can only accept one). It's good for you and for the answerer. – Rick Decker Jan 23 '13 at 17:03

Steven has essentially given you the answer (with one minor error). Here's how one might arrive at it. I'll do one half of the derivation; the other half is the same, but you'd interchange most of the $\le$ and $\ge$ and replace every big-O with big-$\Omega$.

You know that $T(n) = T(n-1)+\Theta(n)$ so you know that $T(n) = T(n-1)+O(n)$ and so there is a $c>0$ such that $$T(n)\le T(n-1)+cn$$ for all $n$ sufficiently large. We're been handed our guess, namely that $T(n)=O(n^2)$ so our guess will be that $T(n)\le kn^2$ for some $k>0$ and all $n$ sufficiently large. In the discovery phase, we'll try to find a $k$ in terms of the $c$ we have.

For our $k$ we have \begin{align} T(n)&\le T(n-1)+cn\\ &\le k(n-1)^2+cn \end{align} and we require that $T(n)\le k(n-1)^2+cn\le kn^2$. We have this chain of results \begin{align} k(n-1)^2+cn&\le kn^2\\ k(n^2-2n+1)+cn&\le kn^2\\ kn^2-2kn+k+cn&\le kn^2\\ -2kn+k+cn&\le 0\\ k(1-2n)&\le-cn\\ k(2n-1)&\ge cn\\ k&\ge \frac{cn}{2n-1} \end{align} so since the largest value of $n/(2n-1)$ for $n\ge 1$ is $1$, any $k\ge c$ will work. Let's see that this does indeed work with $k=c$. \begin{align} T(n)&\le T(n-1) +cn &\text{given}\\ &\le c(n-1)^2+cn &\text{by assumption}\\ &=cn^2-2cn+c+cn\\ &=cn^2-cn+c\\ &=c(n^2-n+1)\le cn^2 &\text{ta daa!} \end{align} as long as $n\ge 1$, so indeed $T(n)=O(n^2)$. As I said, the other direction is immediate.

-

IMHO, a better way of phrasing the question would be: "if $g(n)\in\Theta(n)$ and $T(n)$ is defined by $T(n) = T(n-1)+g(n)$, show that $T(n)\in\Theta(n^2)$"; this stresses the role of $\Theta(n)$ as a class of functions, not an individual one.

A place to start would be to rewrite your recursive definition of $T(n)$ into a more explicit one: if you expand out a few steps of the recursion, a pattern should become clear ($T(n) = T(n-1)+g(n) = T(n-2)+g(n-1)+g(n)=\ldots$); can you figure out how to use this to write a definition of $T(n)$ that doesn't involve the recursion?

Once you have the expression from your expansion of the recursive definition of $T()$, you can start plugging in the machinery around the $\Theta()$ notation: the definition of the class $\Theta(n)$ is that $g(n)\in\Theta(n)$ if there are constants $g_1$ and $g_2$ such that for all $n$, $g_1\cdot n\leq g(n)\leq g_2\cdot n$. The lower and upper bounds on individual values of $g()$ should let you bound the expression you found in the first step; you may want to keep in mind the formula that $\sum_{i=0}^n i = \frac{n(n+1)}{2}$.

Finally, once you have a new set of bounds for your function $T()$ you can go the other way, and try to find new constants $T_1$ and $T_2$ such that $T_1\cdot n^2\leq T(n)\leq T_2\cdot n^2$ for all $n$. (Note that $T_1$ and $T_2$ will have to be expressed in terms of the constants $g_1$ and $g_2$ that you're guaranteed for $g()$.) Once you have these you'll have proven your assertion that $T(n)\in\Theta(n^2)$.

To do the problem with the substitution method, a similar approach can be taken; here you'd start by picking 'constants' $T_1$ and $T_2$ (to be specified later) for the definition of $T(n)\in\Theta(n^2)$, as well as assuming the constants $g_1$ and $g_2$ specified by the problem's condition that $g(n)\in\Theta(n)$. You can then say that \begin{align} T(n) &= T(n-1)+g(n) \\ &\leq T(n-1) + g_2\cdot n && \text{by the definition of g(n)\in\Theta(n)} \\ &\leq T_2\cdot (n-1)^2+g_2\cdot n&& \text{by the definition of T(n)\in\Theta(n^2)} \\ &=T_2 n^2+(g_2-2T_2)n+T_2&& \text{by algebra} \\ \end{align} And so you need to find a way of choosing a $T_2$ such that $T_2n^2+(g_2-2T_2)n+T_2\leq T_2\cdot n^2$ for all $n$ (Hint: try subtracting $T_2n^2$ from both sides to see what you're left with). A similar approach will handle the other side of the inequality in the $\Theta()$ definition.

-
Hey steven and thanks for taking the time to help me wth my prob. I already knew how to solve the problem by expanding the formula. However, the question clearly states that it should be solved using the substitution method.. Meaning you guess a solution and plug it in the place of n. Do you understand or have I got it all wrong? – Peter Jan 21 '13 at 23:31
@Peter Sorry - I tend to gloss over question titles, and the body of the question nowhere indicates that it needs to be done via the substitution method. I'll amend my response to address that. – Steven Stadnicki Jan 21 '13 at 23:36
Thank you Steven. I appreciate it. Once you update your answer I will accept your answer as the correct answer to my question – Peter Jan 21 '13 at 23:40
@Peter I encourage you to wait, actually, to see if any other answers show up over the next few hours - questions with accepted answers tend to get less attention, and someone may well come along with a much better answer than mine that would deserve recognition! – Steven Stadnicki Jan 21 '13 at 23:48
One minor goof. In your display, the 1 on the right side of the last line should be $T_2$. – Rick Decker Jan 22 '13 at 2:48