Notaciones Asintóticas
Enviado por Alexander Zavaleta Calderon • 22 de Octubre de 2018 • Apuntes • 1.455 Palabras (6 Páginas) • 69 Visitas
¿Cuáles de las siguientes afirmaciones son verdaderas? Demuestre sus respuestas. a. 𝒏𝟐 ∈ 𝑶(𝒏𝟑)
b. 𝒏𝟐 ∈ 𝛀(𝒏𝟑)
c. 𝟐𝒏 ∈ 𝜽(𝒏𝟐)
d. 𝒏! ∈ 𝜽((𝟐𝒏 + 𝟏)!)
e. 𝟑𝒏𝟑 + 𝟐𝒏𝟐 ∈ 𝑶(𝒏𝟑)
f. 𝟑𝒏 ∈ 𝑶(𝟐𝒏)
g. 𝒏𝟑 + 𝟐𝒏𝟐 ∈ 𝛀(𝒏𝟑)
h. 𝟑𝒏𝟑 𝑛𝑜 ∈ 𝑶(𝟐𝒏)
es CIERTO pues[pic 2]
𝒏𝟐
[pic 3]
𝐥𝐢𝐦 ( 𝟑) = 𝟎
𝒏→∞ 𝒏
[pic 4]
Consideramos 𝑓(𝑛) = 𝑛2 y 𝑔(𝑛) = 𝑛3 y aplicamos el teorema del límite como sigue:
lim (
𝑛2
3) = lim ([pic 5]
2 ∗ 𝑛 2
2) = lim ([pic 6][pic 7]
) = 0
𝑛→∞ 𝑛
𝑛→∞
3 ∗ 𝑛
𝑛→∞
6 ∗ 𝑛
Esto significa que 𝒏𝟑 crece más rápido que 𝒏𝟐. En este caso, podríamos afirmar que es FALSO.
es FALSO pues[pic 8]
𝒏𝟐 .
[pic 9]
𝐥𝐢𝐦 ( ) = 𝟎[pic 10]
𝒏→∞
𝒏! ∈ 𝜽((𝟐𝒏 + 𝟏)!)
En este caso, no es posible usar L’Hôpital por ser una factorial. Por lo que usaremos un método distinto. Siendo este el siguiente:
𝒏!
= 𝐥𝐢𝐦[pic 11]
𝒏→∞ (𝟐 ∗ 𝒏 + 𝟏)!
= 𝐥𝐢𝐦[pic 12]
(𝒏) ∗ (𝒏 − 𝟏) ∗ … ∗ 𝟏
= 𝟎
𝒏→∞ (𝟐 ∗ 𝒏 + 𝟏) ∗ (𝟐 ∗ 𝒏) ∗ (𝟐 ∗ 𝒏 − 𝟏) ∗ … ∗ (𝒏) ∗ (𝒏 − 𝟏) ∗ … ∗ 𝟏
Vemos que al desarrollar el factorial podemos eliminar muchos valores. En este caso, el resultado es 0, ya que 𝒈(𝒏) crecerá más rápido que
𝒇(𝒏).
Por consiguiente, es FALSO porque 𝒇(𝒏) ∉ 𝛀(𝒈(𝒏)). Por la tanto, 𝒇(𝒏)) ∉
𝛉(𝒈(𝒏)).
𝟑𝒏𝟑 + 𝟐𝒏𝟐 ∈ 𝑶(𝒏𝟑)
Sean 𝒏𝟎 = 𝟎 y 𝒄 = 𝟓.
Entonces, para 𝒏 ≥ 𝟎, existe 𝒄 = 𝟓, tal que
𝟑𝒏𝟑 + 𝟐𝒏𝟐 ≤ 𝟓𝒏𝟑
Es CIERTO.
es FALSO pues[pic 13]
𝟐𝒏
𝐥𝐢𝐦 ( 𝒏) = 𝟎[pic 14]
𝒏→∞ 𝟑
[pic 15]
Sean 𝒄 = 𝟏 , entonces
𝑻(𝒏) ≥ 𝒄 𝒏𝟑 , para 𝒏 = 𝟎, 𝟏, 𝟐, …
Es CIERTO.
𝟑𝒏𝟑 ∉ 𝑶(𝟐𝒏) es FALSO pues 𝐥𝐢𝐦 ( 𝟐𝒏 ) = ∞.[pic 16]
𝒏→∞
𝟑𝒏𝟑
Comparar los siguientes pares de funciones usando la notación asintótica. En cada caso establecer si f(n) ϵ O(g(n)), f(n) ϵ Ω(g(n)), f(n) ϵ θ(g(n)).
f(n) g(n)
10−3𝑛4 10−3𝑛3
𝑛2 𝑛 𝑙𝑜𝑔 𝑛
𝑙𝑜𝑔(𝑛) 𝑙𝑜𝑔(𝑙𝑜𝑔 𝑛)
22𝑛 𝑛2𝑛
100𝑛 + 𝑙𝑜𝑔10𝑛 𝑛 + (𝑙𝑜𝑔 𝑛)2
𝑙𝑜𝑔(𝑛) 𝑙𝑜𝑔 𝑛2
...