Big O estimate of simple while loop Give a big-O estimate for the number of operations, where an operation is an addition or a multiplication, used in this segment of an algorithm (ignoring comparisons used to test the conditions in the while loop).
i := 1
t := 0
while i ≤ n
   t := t + i
   i := 2i

My attempt:
n = 1       i=2
n = 2       i=4
n = 3       i=8
n = 4       i=16

relationship of i to iteration is i = 2^n
How many iterations(n’) until 2^(n’) > n (basically solving for n')
n’ > log2(n) thus the big O estimate is:
O(log_2(n)) (read as log base 2 of n)

However, the book says it's O(log(n)) - why isn't it base 2?

$O(\log_2(n))$ and $O(\ln{n})$ are the same thing, since $\log_2$ and $\ln$ are related by the formula
$$\log_2{n} = \frac{\ln{n}}{\ln{2}} \approx 1.44 \ln{n}$$
The multiplicative constant is irrelevant for the Big O notation.

More precisely, we have the relations
$$1.44 \ln{n} \le \log_2{n} \le 1.45 \ln{n}$$
