La complessità temporale del seguente algoritmo?

Question

Sto imparando notazione O-grande in questo momento e siamo imbattuti in questo piccolo algoritmo in un altro thread:

i = n 
while (i >= 1) 
{ 
    for j = 1 to i // NOTE: i instead of n here! 
    { 
     x = x + 1 
    } 
    i = i/2 
} 

Secondo l'autore del post, la complessità è Θ (n), ma non posso capire come. Penso che la complessità del ciclo while sia Θ (log (n)). La complessità del ciclo for da quello che stavo pensando sarebbe anche Θ (log (n)) perché il numero di iterazioni si sarebbe dimezzato ogni volta.

Quindi, la complessità dell'intera cosa non dovrebbe essere Θ (log (n) * log (n)) o sto facendo qualcosa di sbagliato?

Edit: il segmento è nel migliore risposta di questa domanda: https://stackoverflow.com/questions/9556782/find-theta-notation-of-the-following-while-loop#=

Answer 1

Immaginate per semplicità che n = 2^k. Quante volte viene incrementato x? Ne consegue facilmente questo è Geometric series

2^k + 2^(k - 1) + 2^(k - 2) + ... + 1 = 2^(k + 1) - 1 = 2 * n - 1

Quindi questa parte è Θ(n). Ancheget è dimezzato k = log n volte e non ha effetto asintotico su Θ(n).

Answer 2

Il valore di i per ogni iterazione del while loop, che è anche il numero di iterazioni del ciclo for ha, sono n, n/2, n/4, ... e la complessità complessiva è la somma di quelli. Questo lo mette all'incirca a 2n, che ti dà il tuo Theta (n).