Test cuestionario sobre notación Big O

Ejemplos de preguntas de la prueba

• 1Una búsqueda binaria recursiva pasa únicamente índices del arreglo y crea una llamada recursiva en cada nivel. ¿Cuál es la complejidad del espacio auxiliar de la pila de llamadas?
  • O(n), porque el arreglo original contiene n elementos.
  • O(1), porque cada marco de pila individual tiene tamaño constante.
  • O(log n), porque se agrega un marco en cada nivel mientras el rango de búsqueda se reduce repetidamente a la mitad.
  • O(n log n), porque el tamaño del arreglo se combina con la profundidad de la recursión.
• 2Un algoritmo realiza 4n² + 3n + 20 operaciones básicas. ¿Cuál es su tiempo de ejecución asintótico ajustado?
  • Tiempo cuadrático, porque el término n² domina a medida que n crece.
  • Tiempo lineal, porque se eliminan los términos de orden inferior y las constantes.
  • Tiempo logarítmico, porque solo importa la cantidad de dígitos del tamaño de la entrada.
  • Tiempo cúbico, porque la expresión contiene tres términos distintos.
• 3Si un algoritmo tarda Θ(n²), aproximadamente ¿cómo cambia su cantidad de trabajo cuando n se duplica para valores grandes de n?
  • Se vuelve aproximadamente cuatro veces mayor.
  • Se vuelve aproximadamente dos veces mayor.
  • Se vuelve aproximadamente ocho veces mayor.
  • Permanece aproximadamente igual.