[Math] Big O estimate of simple while loop

algorithmsasymptotics

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?

Best Answer

$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}$$

Related Question