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 := 2iMy attempt:
n = 1 i=2
n = 2 i=4
n = 3 i=8
n = 4 i=16relationship 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?
1 Answer
$\begingroup$$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}$$
$\endgroup$ 1
