¿Por qué $ \ log n + \ log \ frac {n} {2} + \ log \ frac {n} {4} + \ log \ frac {n} {8} + \ \ cdots + \ log \ frac {n} {n}=Theta (\ log ^ 2 n) $?

Question

$$ \ log n + \ log \ frac {n} {2} + \ log \ frac {n} {4} + \ log \ frac {n} {8}+ \ CDOTS + \ LOG \ FRAC {N} {N}=THETA (\ LOG ^ 2n). $$

La suma de logaritmos es el logaritmo del producto $ n \ cdot \ frac {n} {2} \ cdot \ frac {n} {4} \ cdot \ frac {n} {8} \ cdots \ frac {n} {n} $ .Esto es igual a $ n ^ {\ log n} $ dividido por qué?Si el producto simplemente sería $ n ^ {\ log n} $ , entonces esto haría perfecto sente desde $ \ log(n ^ {\ log n})=log (n) \ cdot \ log (n)=log ^ 2 n $ .Pero el divisor es igual a $ \ frac {1} {2} \ cdot \ frac {1} {4} \ cdot \ frac {1} {8} \ cdot \ frac {1}{16} \ CDOTS \ FRAC {1} {N} $ Así que no lo entiendo.

Answer 1

Suponiendo $ n $ es una potencia de $ 2 $ , tiene: $$ \ sum_ {i= 0} ^ {\ log n} \ log \ frac {n} {2 ^ i}= \ sum_ {i= 0} ^ {\ log n} \ izquierda (\ log n - i \ derecha)= \ sum_ {i= 0} ^ {\ log n} i= \ frac {(\ log n) (\ log n + 1)} {2}=theta (\ log ^ 2 n). $$