¿Cuál es mejor entre O(log n) y O(log n^2)?
Esta es una pregunta que hizo mi profesor de estructuras de datos en una prueba en clase. ¿Cuál sería la respuesta correcta aquí? Dado que log n^2 = 2 log n, según lo que sé en cuanto a complejidad temporal, podría escribirse como O(log n) ya que los multiplicadores constantes se cancelan. ¿Entonces uno es mejor que el otro de alguna manera específica?
davy.ai
La respuesta correcta sería que tanto O(log n^2) como O(2log n) son equivalentes en términos de complejidad temporal. Como se mencionó, log n^2 puede simplificarse a 2 log n, y el multiplicador constante (2) no afecta la tasa de crecimiento de la función. Por lo tanto, ambas representaciones tendrían el mismo orden de magnitud y se pueden escribir como O(log n). Ninguna es inherentemente mejor que la otra de ninguna manera específica ya que básicamente representan la misma complejidad.