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!
On
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.