Liczba operatorów dodających i mnożących w tym algorytmie - duża-o, teoria złożoności, złożoność asymptotyczna

Rozważmy następujący algorytm:

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

Chcę dowiedzieć się, ile dodatkówi operacje mnożenia ten algorytm wykonuje; mam jednak kłopoty. Rozumiem, że wartość i podwaja się po każdej iteracji, ale nie wiem, jak uogólnić algorytm, aby podać prawidłową liczbę operacji aż do wartości n. Jeśli ktoś może rzucić nieco światła na tę kwestię, byłbym bardzo wdzięczny.

Dziękuję Ci!

Odpowiedzi:

Ponieważ wartość i podwaja każdą pętlę i i <= n

i*2^x <= n

a maksymalizacja x daje liczbę pętli. Ponieważ i = 1

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

i wykonujemy 1 dodawanie i 1 mnożenie na pętlę. Myślę, że możesz wziąć to stąd :)