Proving Big Omega Fonction

Question

J'essaie de trouver le n0 (n non) d'une fonction avec une grande taille oméga de n^3 où c =

2,25

() = 3^3-39^2 + 360 + 20. Pour prouver que() est Ω (^ 3), nous avons besoin de constantes, 0> 0 telles que() ≥^3 pour chaque ≥ 0

Si c = 2.25, comment trouver le le plus petit entier qui satisfait n0? Ma première pensée était de brancher n = 1, parce que n> 0, et si l'inégalité travaillée n = 1 serait le plus petit n (donc n0). Mais, l'inégalité doit être satisfaite pour tout n> = n0, et si je branche, par exemple, n = 15, l'inégalité ne fonctionne pas.

Answer 1

Pensez-y comme ceci. Après un certain point 3^3 - 39^2 + 360 + 20 sera toujours supérieur ou égal à n^3 pour le simple fait que finalement 3n^3 battra le -39n^2. Donc F (n) ne descendra jamais en dessous de n^3 pour un nombre extrêmement grand. Vous n'avez pas besoin de mettre le minimum nO, il suffit de choisir un nombre extrêmement grand pour nO, puisque la question demande après une certaine valeur pour n, l'énoncé restera vrai pour toujours. Choisissez nO, par exemple, pour être un nombre extrêmement grand X, puis utilisez une preuve inductive où X est le cas de base.

Answer 2

Vous pouvez résoudre ce problème mathématiquement. Pour vous assurer que je comprends ce que vous voulez, je vais résumer ce que vous demandez. Vous voulez trouver le plus petit entier n pour que:

3^3 - 39^2 + 360 + 20 ≥ 2,25^3 (1)

Et tout autre entiers plus grand que n doit également satisfaire à l'équation (1).

Voici donc ma solution:

(1) < => 0,75^3-39^2 + 360 + 20 ≥ 0

Soit f (n) = 0,75^3-39^2 + 360 + 20

f (n) = 0 < => n1 = n2 = -0,05522 ou 12,079 ou n3 = 39,976

• Si n < n1, f (n) < 0 (essayez vous-même)
• Si n1 < n < n2, f (n)> 0 (le signe alternera)
• Si n2 < n < n3, f (n) < 0 (le signe alterne , encore une fois)
• Si n> n3, f (n)> 0

donc, pour répondre à vos besoins, la valeur minimale de n doit être 40