2

I am studying for an exam, and one practice problem I attempted asks me to prove that:

$T(n) = T(n - 2) + n^2 = O(n^3)$

I need to use the induction/substitution method for this problem. My proof attempt is below. Is this correct? If so, is there a more concise way to do this?

We claim that $T(n) = O(n^3)$. To prove this, we need to show that $T(n) \leq Cn^3$ $\forall n > n_0$ (for any positive constants $C$ and $N_0$). We prove this as follows:

\begin{align} T(n) &= T(n - 2) + n^2 &&\\ &\leq C(n - 2)^3 + n^2 \text{ (by inductive hypothesis)} &&\\ &= Cn^3 - 6Cn^2 + 12Cn - 8C + n^2 &&\\ &= X \end{align}

In order for our proof to hold, we must show that $X < Cn^3$:

\begin{align} X &\leq Cn^3 &&\\ Cn^3 - 6Cn^2 + 12Cn - 8C + n^2 &\leq Cn^3 &&\\ -6Cn^2 + 12Cn - 8C + n^2 &\leq 0 &&\\ -6Cn^2 + 12Cn - 8C &\leq -n^2 &&\\ C(-6n^2 + 12n - 8) &\leq -n^2 &&\\ C(6n^2 - 12n + 8) &\geq n^2 \text{ (multiply by -1)} &&\\ C &\geq \frac{n^2}{6n^2 - 12n + 8} \text{ (assumes $n \geq 2$)} \end{align}

The right-hand-side of this equation is always less than or equal to one if $n \geq 2$. Thus, if we simply choose $C = 1$ and $n_0 = 3$, $T(n) \leq Cn^3$, which is what we set out to prove. It follows by the principle of induction that $T(n) \leq 1 * n^3$ $\forall n > 3$, and thus that $T(n) = O(n^3)$.

uniquesolution
  • 18,541
Daniel
  • 189

1 Answers1

1

The calculation you did looks fine, but there are some technical issues with how you infer the $O(n^3)$ from it and they involve the base cases.

For instance, you claim at the end that $T(n) \leq n^3$ for $n \geq n_0$. However, I would tell you that this is not true. For instance, if you start out with $T(1) = T(2) = 100^3$, then define $T$ recursively, then $T(n) \leq n^3$ false for all $n \geq 2$. It is true eventually because $1^2 + 2^2 + \cdots + n^2 = \frac{1}{3}n^3 + \mbox{lower order terms}$, but the bound for $n_0$ is incorrect.

In particular, I would ask you to look at where you got $C$ from: you cannot pick it arbitrarily. This was a subtlety that I did not see in the first question that you asked, but is actually very important.

Also, if you were to tell me that $n_0 \geq 2$, then I would have agreed before doing the calculation, because $T(n - 2)$ does not make sense unless $n -2$ is at least the minimum value that $T$ is defined on. This is also another subtlety that is important.

The second problem with the induction is that you are inducting on the even numbers and odd numbers separately (which is why I defined $T$ above on $1$ and on $2$), because we are looking at $T(n-2)$ and not $T(n)$. In particular, the $C$ that you pick should rely on both the base cases.

user357980
  • 1,854
  • Thank you for the very detailed answer. My professor mentioned that we can ignore base cases for the purpose of this class/exam. Given that - would you say the proof I gave is sufficient? – Daniel Feb 25 '18 at 00:27
  • Well, I don't know what "sufficient" means. If "sufficient" means sufficient for your exam, then I suppose that an instructor would be of better help. If "sufficient" means sufficient for showing that the result is actually true, then I would say not for the reasons that I laid out: Base cases are incredibly important in general. – user357980 Feb 25 '18 at 04:02
  • I suppose that the professor saying "you can ignore base cases" can be said when one already knows that base cases are trivial. In this case, one would say something like: "Now, we can find a constant $C$ that works for the base cases and then we can replace it with a possibly larger number that is greater than $1$, so that the Inductive Hypothesis holds." In the kinds of problems that you are looking at (these recurrence relations with finding a bound for a fixed number of constants) then it seems plausible that the calculations are all that is needed, given that you understand the ideas. – user357980 Feb 25 '18 at 04:08
  • Ah, I see. Yes, we are allowed to assume that the base cases are trivial. Thank you for the help. – Daniel Feb 25 '18 at 14:37