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

Answer 1

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

I don't understand how it grows (other than rather ripidly), let alone how quickly it approaches n.

Answer 2

Generally BIG'O notation is asymptotic analysis so it considers only average case.... so for above case 4,5 line both assignments are considered as one operation and since we are iterating n times the complexity is O(n).

Answer 3

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

Hope this helps =)

Answer 4

@ndan ... your right ,Im sorry i didnt see the relation between i and t ... thanks for the correction