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.
Best Answer
Regarding the first recurrence:
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:
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.