Es esta la prueba de big O, ¿correcto?

Question

Mostrar que $n^2 -10\notin O(n)$

Mi amigo sigue insistiendo en que mi prueba es incorrecta. Podría por favor decirme si hay un error? (hechos propuso editar)

Prueba:

Supongamos que al contrario que $n^2 -10\in O(n)$. Por definición, esto significa que no existe $c >0$ $n_0 > 0$ tal que $n^2 - 10 \leq cn, \forall n>n_0$. Deje $n = n_0 + c + 10$,

a continuación, $(n_0 + c + 10)^2 - 10 \leq c(n_0 + c + 10)$

$\Rightarrow$ $(n_0 + c)^2 + 2(10)(n_0+c) + 90 - cn_0 -c^2 - 10c \leq 0$

$\Rightarrow$ $(n_0^2 + 2n_0c + c^2) + 20n_0+20c + 90 - cn_0 -c^2 - 10c \leq 0$

$\Rightarrow$ $n_0^2 + n_0c + 20n_0+10c + 90 \leq 0$. Desde $n_0$ $c >0$ El lado izquierdo es siempre mayor que $0$. Una contradicción. Por lo tanto $n^2 -10\notin O(n)$.

Answer 1

Esta prueba es correcta. Es un poco extraño - intuitivamente, no es inmediatamente obvio para mí que si la identidad se mantiene para algunos $n_0$, entonces no se puede sostener por $n_0 + c + 10$, en particular - tal vez no lo suficiente?

Pero la prueba muestra que es, y me gusta porque es atípico.

Answer 2

Este es correcta. También se señala la alternativa de caso, y luego procede a la conclusión y muestra una contradicción. Según el pato de la prueba, si es que nada como un pato, vuela como un pato, y grazna como un pato, es un pato. Por lo tanto se pasa el pato de la prueba. Yo no veo nada de malo.