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