1

Tengo una duda respecto al algoritmo de ordenamiento Mergesort.

He visto en algunos foros que la complejidad es O(nlog(n)), pero en otros dicen que es O(nlog2(n)) (logaritmo de n en base 2). En algunos videos también veo que dicen lo mismo: unos dicen que es el primero, pero otros dicen que es el segundo. Por lo que me genera confusión. ¿Me podrían explicar?

1
  • 1
    Es lo mismo, O(nlog(n)) es lo mismo que O(nlog2(n))
    – Japv
    el 21 jun. 2021 a las 20:43

1 respuesta 1

1

Extendiendo el comentario de @Japv. Cuando trabajamos con la notación "O grande" (Big O) la base en la que se encuentre el logaritmo es indiferente, ya que el resultado siempre va a ser el mismo, por lo tanto se cumple lo siguiente:

O(log2 N) = O(log10 N) = O(loge N)

Esto se debe a las propiedades de los logaritmos y a que la notacion "O grande" hace que todos lo logaritmos en diferentes bases estén relacionados por un factor constante, por lo tanto se puede transformar la base del logaritmo de dos a diez o a "N" y el resultado seguirá siendo el mismo.

Documentación sobre logaritmos

1
  • 1
    Mucha gracias. Ya logré entender más por la documentación y tu explicación.
    – Leonardo
    el 23 jun. 2021 a las 16:32

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.