Počet operátorov pridávania a násobenia v tomto algoritme - big-o, complexity-theory, asymptotic-complexity

Zvážte nasledujúci algoritmus:

i := 1
t := 0
while i ≤ n
t := t + i
i := 2i

Mám záujem zistiť, koľko navyšea multiplikačné operácie, ktoré tento algoritmus vykonáva; Ja sa však dostávam do problémov. Rozumiem, že hodnota i sa zdvojnásobí po každej iterácii, ale neviem, ako zovšeobecniť algoritmus, aby sme dali správny počet operácií až do hodnoty n. Ak niekto vie túto záležitosť objasniť, veľmi si to vážim.

Ďakujem!

odpovede:

Vzhľadom k tomu, hodnota i zdvojnásobí každú slučku a i <= n

i*2^x <= n

a maximalizácia x udáva počet slučiek. Pretože i = 1

2^x = n
x = floor log(n)

a vykonáme 1 sčítanie a 1 násobenie na slučku. Myslím, že si to môžete vziať odtiaľto :)