Question

Give a big-O estimate for the number of operations, where an operation is anaddition or a multiplication,used in this segment of an algorithm (ignoring comparisons used to test the conditions in the while loop).

$\begin{array}{r}\mathbf{i}\mathbf{:=}\mathbf{1}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{t}\mathbf{:=}\mathbf{0}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{\text{while}}\mathbf{i}\mathbf{\le }\mathbf{n}\\ \mathbf{t}\mathbf{:=}\mathbf{t}\mathbf{+}\mathbf{i}\\ \mathbf{i}\mathbf{:=}\mathbf{2}\mathbf{i}\end{array}$

Short answer

The complexity of the given algorithm is O(log n).

Step-by-step solution

Given algorithm:

The given algorithm is

$\begin{array}{r}i:=1\\ t:=0\\ \text{while}i\le n\\ t:=t+i\\ i:=2i\end{array}$

Finding the number of operations in the algorithm:

Consider n = 1 for n = i

Then,

$$\begin{gathered} i=2i \\ =2\times 1 \\ =2 \end{gathered}$$

If n = 2

Then,

$$\begin{gathered} i=2i \\ =2\times 2 \\ =4 \end{gathered}$$

If n = 3

Then,

$$\begin{gathered} i=2i \\ =2\times 3 \\ =6 \end{gathered}$$

Therefore, the value of i is double for every repetition of while loop.

Thus,

$i=2^n$

The value if i is increased at the rate of power of digit 2 since the number of operations is log (2n) .

Therefore, the complexity of the algorithm is O (log n) .