Help with solving recurrence relations using iterative substitution

Question

I need help solving these two recurrences with iterative substitution. I've looked at examples, and tried to follow them, but I just don't understand the whole plugging the recurrence into itself. I tried them out, not sure if they are correct, but if someone can point me in the right direction I would be very greatful!!!

For both assume $T(n) = \theta(1)$ for $n \leq 1$. First recurrence:

$$ \begin{equation} \begin{split} T(n) &= T(n - 2) + 7 \\ & = T(n - 2 - 2) + 7 - 2 \\ &= T(n - 4) + 5 \\ &= T(n - 2^i) + 5 - 2^i \newline &=T(n) =\theta(n) \end{split} \end{equation} $$

Second recurrence:

$$ \begin{equation} \begin{split} T(n) &= nT(n - 1) + 1 \\ & = nT(n - 1 - 1) + 1 \\ &= n^2T(n - 2) + 1 \\ &= n^iT(n - i) + 1 \\ &= \theta(n) \end{split} \end{equation} $$

I'm pretty sure the last one is wrong, I'm guessing it is $\log (n)$ from when I use the master theorem on it instead. I'm not sure though.

Answer 1

Regarding the first recurrence:

\begin{align} T(n) &= T(n - 2) + 7 \\ &= T(n - 2 - 2) + 7 - 2 \end{align}

Should it not be $$ T(n-2) \mapsto T(n-4)+7 $$

and

\begin{align} T(n) &= T(n - 2) + 7 \\ &= (T((n - 2) - 2) + 7) + 7 \\ &= T(n + 2\cdot (-2)) + 2\cdot 7 \\ &= \vdots \\ &= T(n + k\cdot (-2)) + k\cdot 7 \end{align}

instead?

Regarding the second recurrence:

\begin{align} T(n) &= nT(n - 1) + 1 \\ & = nT(n - 1 - 1) + 1 \end{align}

This should be

$$ T(n-1) \mapsto (n-1) T(n-2) + 1 $$

and

\begin{align} T(n) &= n T(n - 1) + 1 \\ &= n ((n-1) T(n - 2) + 1) + 1 \\ &= n(n-1) T(n - 2) + n + 1 \end{align}

The resulting expression might be useful, if the argument of $T$ is reduced to some known initial value.

Answer 2

You may find the following trick to be useful. Write down a separate "reference" copy of the recurrence using a different variable: $$T(m)=T(m-2)+7$$ Now you're going to apply this recurrence with various values plugged in for $m$, and you can record what $m$ you picked each time so you don't get confused: $$\begin{align} T(n)&=T(n-2)+7\,\,&[m=n]\\ &= (T(n-2 -2)+7) +7\,\,&[m=n-2]\\ &= T(n-4)+ 2\cdot 7\\ &= (T(n-4-2)+7)+2\cdot 7\,\,&[m=n-4]\\ &= T(n-6)+3\cdot7\\ &\,\,\vdots\\ &=T(n-2k) +k\cdot7 \end{align}$$ Taking $k=n/2+O(1)$ we get $$T(n)=O(1)+7(n/2+O(1))= \Theta(n).$$

The same trick helps with the others.