Por que$\ logn+\ 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}+ \ cdoz + \ log \ frac {n} {n}=theta (\ log ^ 2n). $$

A soma dos logaritmos é o logaritmo do produto $ n \ cdot \ frac {n} {2} \ frac {n} {4} \ cdot {4} \ cdot \n} {8} \ cdots \ frac {n} {n} $ .Isso é igual a $ n ^ {\ log n} $ dividido por quê?Se o produto seria apenas $ n ^ {\ log n} $ , então isso faria perfeito Sende desde $ \ log(n ^ {\ log n})=log (n) \ cdot \ log (n)=log ^ 2 n $ .Mas o divisor é igual a $ \ frac {1} {2} \ frac {1} {4} \ cdot \ frac {1} {8} \ cdot \ frac {1}{16} \ cdots \ frac {1} {n} $ então eu não entendi.

Answer 1

Assumindo $ n $ é um poder de $ 2 $ , você tem: $$ \ sum_ {i= 0} ^ {\ log n} \ log \ frac {n} {2 ^ i}= \ sum_ {i= 0} ^ {\ log n} \ left (\ log n - i \ direita)= \ sum_ {i= 0} ^ {\ log n} i= \ frac {(\ log n) (\ log n n + 1)} {2}=theta (\ log ^ 2 n). $$