¿lg(n-i) es Omega de lg(n)?
Estoy tratando de calcular la expresión a continuación.
El punto donde no puedo entender es de la línea 3 a la línea 4.
Creo que después de la línea 3, la expresión se convierte en:
Sigma(i=1 to n-1) (lg(n-i))
Pero, ¿podemos escribirlo como en la línea 4?
No estoy seguro de que lg(n-i) sea Omega de lg(n).
Y si es posible, también quiero una explicación intuitiva.
Gracias.
davy.ai
La expresión dada en la imagen se puede simplificar como:
Ahora, intentemos simplificar esto aún más basándonos en la condición dada:
“`
lg(n-i+1) – lg i >= c * lg n // donde c es alguna constante
=> lg(n+1) – lg(i) >= c * lg n
=> lg(n+1) – c * lg n >= lg i
Dado que
lg(n+1) - c * lg nes una constante, llamémoslak. Por lo tanto, podemos escribir:lg i <= k // es decir, lg i está acotado por una constante
Ahora, sustituyendo esto en la expresión original:
Sigma(i=1 to n-1) (lg(n-i+1) – lg(i))
= Sigma(i=1 to n-1) lg(n-i+1) – Sigma(i=1 to n-1) lg(i)
<= n * lg(n+1) – Sigma(i=1 to n-1) lg i // usando el hecho de que lg i <= k para todo i
= n * lg(n+1) – lg(n-1)! // usando la propiedad de los logaritmos
= Theta(n * lg n) // usando la aproximación de Sterling
Por lo tanto, podemos escribir la expresión como Theta(n * lg n). Por lo tanto, no es posible escribirlo como Omega(lg n). Además, intuitivamente, podemos ver que a medida que el valor de i disminuye de n-1 a 1, log(n-i+1) aumenta y log i disminuye. Entonces, la contribución del primer término domina sobre el segundo término, lo que lleva a una complejidad de Theta(n * log n).