Question

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.

$\begin{array}{r}\mathbf{t}\mathbf{:=}\mathbf{0}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\\ \mathbf{\text{for}}\mathbf{i}\mathbf{:=}\mathbf{1}\mathbf{\text{to}}\mathbf{3}\\ \mathbf{\text{for}}\mathbf{j}\mathbf{:=}\mathbf{1}\mathbf{\text{to}}\mathbf{4}\\ \mathbf{t}\mathbf{:=}\mathbf{t}\mathbf{+}\mathbf{i}\mathbf{j}\mathbf{}\mathbf{}\end{array}$

Short answer

Big-O estimate of the number of operations (where an operation is an addition or a multiplication) is O(1) .

Step-by-step solution

Given algorithm:

The given algorithm is

$\begin{array}{r}t:=0\\ \text{for}i:=1\text{to}3\\ \text{for}j:=1\text{to}4\\ t:=t+ij\end{array}$

Finding the number of operations:

As given that only an addition or a multiplication has to be counted as an operation. We can see that both addition and multiplication operation happens in the last line of the program segment. Thus, there are 2 operations.

The outer loop runs for 3-time steps and the inner loop runs for 4 times steps.

This amounts to a total of $2\times 3\times 4=24$operations.

Since this is a constant number, the complexity of the given algorithm is O(1) .

Therefore, the big- estimate for the number of operations is O(1) .