Give big-o estimate for the number of operations (multiplication or addition) used in the following algorithm segment (ignore comparisons to check while conditions).

i =1
t = 0
while i < = n
i = t+i
t = 2i

'm pretty sure the big O is actually O(log n) Not really a proof but anyway. If you write out the values before each iteration of the loop you get. L - iteration number Lit 110 212 336 4918 52754 681162 So if n was 80 it would take 6 iterations You can see i is growing like 3^(L-2) So if n was 1000 1000 = 3^(L-2) log(1000) [base 3] = L - 2 log(1000) [base 3] + 2 = L 8.287709822868152 = L and if you ceil the answer you get L = 9 and just to check with the table 681162 7243486 87291458 92187 ... The table isn't perfect but hopefully you get the main idea.