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 n ) también son asintóticamente iguales que 2 n + 1 se puede escribir como 2 * 2 n y la multiplicación/suma constante no importa en la notación theta.
2 2n + 1 y O(2 n ) no son lo mismo ya que la constante está en potencia.
Consulte Notaciones asintóticas para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA