Cómo demostrar las relaciones de la gran o

Question

Oye, el título probablemente esté un poco apagado, así que por favor corrígelo si sabes cómo hacerlo mejor.

Como deberes Se me ha dado varias tareas a lo largo de los siguientes:

Sea f (n) y g (n) ser funciones asintóticamente positivos. Demuestre o desmienta cada una de las siguientes conjeturas.

a. f(n) = O(g(n)) implies g(n) = O(f(n)) 

Ahora, mi verdadera pregunta es: ¿cómo harías para probar esto de forma formal? Sé que lo anterior sería fácil, ya que podría proporcionar fácilmente un contraejemplo para refutarlo, pero por el bien del argumento, digamos que queremos hacer esto sin contra ejemplos, como por supuesto esto continúa con algunos otros ejemplos donde Esto no funcionará.

estoy un poco atascado, he las siguientes desigualdades redactado (con < = menor o igual a)

f(n) <= c1 * g(n) 
g(n) <= c2 * f(n) 

Pero no estoy seguro de cómo iba a combinar estos 2 inecuaciones en una sola (en) ecuación y desaprobarla. Estoy seguro de que esto es algo bastante fácil que simplemente he pasado por alto y que estoy siendo bastante estúpido en este momento, pero cualquier sugerencia/ejemplos concretos de cómo hacer esto sería grandioso, para poder trabajar el resto de estas preguntas por mi cuenta.

Answer 1

¿Por qué quiere refutarlo sin usar un contraejemplo? Esa es la forma más directa de refutar un reclamo.

Si tuviera que demostrarlo en su lugar, por supuesto no podría usar un contraejemplo. En este caso, la contrapositiva puede funcionar muy bien: suponga que la afirmación es falsa y luego muestre cómo eso lleva a una inconsistencia lógica.

En este caso, comienza con f(n) <= c1 * g(n) siendo cierto, ya que esto es lo que significa f(n) = O(g(n)). Ahora quiere suponer que g(n) <= c2 * f(n) es verdadero para todos f y g (esta última parte es muy importante, porque ciertamente puede elegir f y g de manera que sea verdadera), y mostrar por qué esto no puede funcionar. Mi sugerencia para ti: escoge un f y un g para que no funcione, y demuéstrale que no puede funcionar por tu elección de c1 y c2.

Answer 2

Unos consejos:
no se olvide que es un f(n) = O(g(n))set notation y puede convertirlo en una forma matemática de las desigualdades.

operaciones sencillas que puede hacer con el O -notation:

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), si c es constante
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(El arte de la programación informática, vol 1 - El O -Notation) relacionada