4938a48b-9d5b-4272-8e50-52ee0d32ebcf
prompter
Can you help me prove Big O notation in LaTeX? Given $T(n)={15n}^3+n^2+4$ prove that $T(n)=O(n^3)$. I'd like a formal induction proof which uses a valid $c$ and $n_0$ value.
a7cf9adb-e112-4657-aa18-f0bfb458aab0
4938a48b-9d5b-4272-8e50-52ee0d32ebcf
assistant
Sure, here's a formal induction proof to show that $T(n)=O(n^3)$ using the Big O notation:

Let $c = 15$ and $n_0 = 1$. Then, for all $n \ge n_0$ we have:

$$T(n) = 15n^3 + n^2 + 4 \le 15n^3 + n^3 + n^3 = 31n^3.$$

Thus, we have $T(n) \le 31n^3$ for all $n \ge n_0$, and it follows that $T(n) = O(n^3)$.

Here's how the above proof would look in LaTeX:
Let $c = 15$ and $n_0 = 1$. Then, for all $n \ge n_0$, we have:

$$T(n) = 15n^3 + n^2 + 4 \le 15n^3 + n^3 + n^3 = 31n^3.$$

Thus, we have $T(n) \le 31n^3$ for all $n \ge n_0$, and it follows that $T(n) = O(n^3)$.