0
$\begingroup$

I am trying to solve a recurrence using substitution method (I am asking for help/confirmation about this solving method, so don't answer with a solution developed by iteration method or something else).
I want to precise that I have just started studying recurrence relations, so I am asking for confirmation of my work.

Given: $$ T(n) = \begin{cases} 1 & n = 1 \\ T(n - 1) + n^2 & n \gt 1 \end{cases} $$

I guess that $T(n) = O(n^3)$, so:
$$ T(n) = T(n \space - \space 1) + n^2 \le c(n - 1)^3 + n^2\\ c(n - 1)^3 + n^2 = cn^3 - 3cn^2 + 3cn - c + n^2 $$

then I continued like this:
$$ cn^3 - 3cn^2 + 3cn - c + n^2 \le cn^3\\ 3cn^2 - 3cn + c - n^2 \ge 0\\ $$

from now on, this is the part about I am not sure if I did it right: $$ n(3cn - 3c - n) \ge -c\\ 3cn - 3c - n \ge -\frac{c}{n}\\ n - 3c \ge -\frac{3c^2 - c}{n}\\ n \ge\ -\frac{3c^2 - c}{n} + 3c $$ Now, I am not sure if i did that right.
I know that this recurrence is a $O(n^3)$, but I want to know if my proof is true.
I want to say that this isn't a homework or something like that, it's a simple exercise that came up to my mind.

EDIT: Let's notice that: $$ 3cn^2 - 3cn + c - n^2 = n^2(3c - 1) - 3cn + c \ge 0 $$ so, all I need to do is to solve this quadratic inequality in order to find for which c values is verified.
Now, I have to calculate the discriminant to check if this inequality has solutions, so: $$ (-3c)^2 - 4(3c - 1)(c) = 9c^2 - 12c^2 - 4c = -3c^2 - 4c = c(3c + 4) $$

Only when the discriminant is greater than zero, the inequality has solutions, and in this case: $$ 3c + 4 > 0\\ 3c > -4\\ c > -\frac{4}{3} $$

From this result, it's proven that $T(n) = O(n^3), \space \forall c > -\frac{4}{3}$
I thought about this proof, is it wrong or did I missed something?

$\endgroup$
2
  • $\begingroup$ One question, what is substitution method? I can't help you if I don't know what method are you using. $\endgroup$
    – Marcos
    Commented Jun 6, 2022 at 16:46
  • $\begingroup$ Substitution method is a solving recurrences method that relies on the induction principle. This method is used to prove upper/lower bounds by induction, just we said in the comments in your answer. For further information, I guess it would be better if you google it. $\endgroup$
    – Francesco
    Commented Jun 6, 2022 at 16:56

1 Answer 1

1
$\begingroup$

To solve the recurrence exactly, you need to assume a more general ansatz: $$T(n) = An^3+Bn^2+Cn.$$ Substitution yields: $$An^3+Bn^2+Cn = A(n-1)^3+B(n-1)^2+C(n-1) + n^2.$$ If we let $n = 1,2,3$, we get the system of equations $$A+B+C = 1,$$ $$7A+3B+C = 4,$$ $$19A+5B+C = 9.$$

$\endgroup$
6
  • $\begingroup$ Thank you, but I do not want to solve the recurrence, I just want to find an upper bound. Have I done it right? $\endgroup$
    – Francesco
    Commented Jun 6, 2022 at 16:05
  • $\begingroup$ you are introducing another constant $k$ into your solution. I'm not sure what this represents. $\endgroup$
    – Doug
    Commented Jun 6, 2022 at 16:14
  • $\begingroup$ omg, I am sorry, i didn't notice that. I guess that I typed "k", by mistake. $\endgroup$
    – Francesco
    Commented Jun 6, 2022 at 16:19
  • $\begingroup$ All right, I have correct the error, now, what do you think? Is my proof correct? $\endgroup$
    – Francesco
    Commented Jun 6, 2022 at 16:26
  • $\begingroup$ In the second line of you inequalities, you should have a negative: $-c/n$ on the right side. $\endgroup$
    – Doug
    Commented Jun 6, 2022 at 16:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .