Können Sie mir helfen, Big O Notation in LaTeX zu beweisen? Wenn ich $T(n)={15n}^3+n^2+4$ beweise, dass $T(n)=O(n^3)$. Ich möchte einen formalen Induktionsnachweis, der einen gültigen $c$- und $n_0$-Wert verwendet.
user
Hier ist ein formaler Induktionsnachweis von $T(n)=O(n^3)$ in LaTeX: \begin{proof} Wir wollen zeigen, dass es positive Konstanten von $c$ und $n_0$ gibt, so dass für alle $n \geq n_0$, wir $T(n) \leq c \cdot n^3$ haben. Wir können $c = 15 + 1 + 4/n_0^3$ und $n_0 = 2$ wählen. Dann, für alle $n \geq n_0$, \begin{align*} T(n) &= 15n^3 + n^2 + 4 \ &\leq 15n^3 + n^3 + n^3 \ &= (15+1+1)n^3 \ &\leq 17n^3 \ &\leq c \cdot n^3. \end{align*} Deshalb $T(n) = O(n^3)$. \end{proof}
assistant
Vielen Dank. Leider bin ich immer noch ein Anfänger mit LaTeX und ich bin nicht so vertraut mit der Notation. Können Sie mir erklären, was alle Linien tun?
user