PUERTA | PUERTA-CS-2003 | Pregunta 20

Considere las siguientes tres afirmaciones

1. (n + k)m = Θ(nm), where k and m are constants
2. 2n + 1 = O(2n)
3. 22n + 1 = O(2n) 

¿Cuáles de estas afirmaciones son correctas?

(A) 1 y 2
(B) 1 y 3
(C) 2 y 3
(D) 1, 2 y 3

Respuesta: (A)
Explicación: (n + k) ^m y Θ(n ^m ) son asintóticamente iguales a La notación theta siempre se puede escribir tomando el término de orden principal en una expresión polinomial.

2 ^{n + 1} y O(2 ⁿ ) también son asintóticamente iguales que 2 ^{n + 1} se puede escribir como 2 * 2 ⁿ y la multiplicación/suma constante no importa en la notación theta.

2 ^{2n + 1} y O(2 ⁿ ) no son lo mismo ya que la constante está en potencia.

Consulte Notaciones asintóticas para obtener más detalles.

Cuestionario de esta pregunta