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 L i t 1 1 0 2 1 2 3 3 6 4 9 18 5 27 54 6 81 162 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 6 81 162 7 243 486 8 729 1458 9 2187 ... The table isn't perfect but hopefully you get the main idea.