Question

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

Answer 1

'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.