Prueba Big-Omega

Question

Así que estoy tratando de resolver este, supongamos que este problema A.

$f(n) = n^2 - 2n$ y $g(n) = n^2$ .

Quiero demostrar que $f(n) \in \Omega(g(n))$ mostrando un conjunto de desigualdades entre $f(n)$ a $g(n)$ para derivar el $c > 0$ y $n_0 > 0$ .

Por ejemplo, digamos

$f(n) = n^2 + 2n$ y $g(n) = n^2$ y $f(n) \in O(g(n))$ .

Claramente, $n^2 + 2n \le n^2 + 2n^2 = 3n^2 \quad \forall n_0>0$ Así, si $c = 3$ y $n_0 > 0$ Hemos demostrado que $f(n) \in O(g(n))$ .

¿Cómo hago esto para el problema anterior, el problema A?

Gracias.

Answer 1

Para los grandes $n$ , $$f(n)=n^2-2n \ge \frac{1}{2} n^2 = \frac{1}{2} g(n).$$ Para encontrar $n_0$ de forma explícita, nota $$n^2-2n - \frac{1}{2}n^2= \frac{1}{2} n(n-4) > 0$$ para $n>4$ .

Answer 2

Tenemos que $f(n) \in \Omega(g(n))$ si existe una constante $c>0$ y un $n_0$ tal que $f(n) \geq c \cdot g(n)$ siempre que $n \geq n_0$ . En otras palabras, $f(n) \in O(g(n))$ si y sólo si $g(n) \in \Omega(f(n))$ .

Si $f(n) = n^2 - 2n$ y $g(n) = n^2$ , debe encontrar un $c > 0$ y un $n_0$ tal que

$$n^2 - 2n \geq c \cdot n^2 \text{ whenever } n \geq n_0$$

Este es el caso si

$$(1 - c)n^2 \geq 2n \text{ whenever } n \geq n_0$$

si $n \geq \frac{2}{1-c}$ . Así que toma $n_0 = \lceil \frac{2}{1-c} \rceil$ .