Come calcolare somma dei quadrati delle serie di log

Question

Ho un algoritmo, e ho capito che la sua complessità runtime segue la seguente formula:

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 

La base del registro è 2.

Come faccio a capire cosa sia il Θ/& Omicron; la complessità algoritmica deriva da questa formula?

Answer 1

per la parte superiore più vincolati si può ragionare similat a log (n!) = O (nlog (n))

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 < [log(n)]^2 + ... + [log(n)]^2 
                  = n[log(n)]^2 

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 = O(n[log(n)]^2) 

lievitare per limite inferiore, hanno bisogno di dimostrare che data somma è> = costante di n [log (n)]^2

Cancellazione prima metà dei termini dalla somma

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= [log(n/2)]^2 + [log(n/2 + 1)]^2 + [log(3)]^2 + ....... + [log(n)]^2 

Sostituzione ogni termine con log (n/2)^2

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= (n/2) * [log(n/2)]^2 

Limite inferiore = (n/2) * [log(n) - 1]^2

Possiamo dimostrare che log(n) - 1 >= (1/2) * log(n)

Quindi limite inferiore = (n/8) * [log(n)]^2 e limite superiore = n * [log(n)]^2

Così Θ([log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2) = n * [log(n)]^2