Question

Give a big-O estimate for the number additions 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}\end{array}$

Short answer

Big-O estimate of the number additions used in the segment provided in the algorithm is $O\left(n^2\right)$.

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 additions:

Consider that the last line of the segment$t:=t+i+j$ is just a one operation.

Now, when the for loop is executed then each time the variable j: = 1 to n is also incremented. This means that the inner for loop executes 2 additions per iteration, as j has to be incremented and the value of t is computed correspondingly.

So, when the loop is executed n times then this implies that there are$\sum _{j=1}^n 2=2n$ additions.

Finding the total number of operations for the entire program:

For every iteration of the outer loop$fori:=1ton$, the inner loop is executed fully and the value of i is incremented.

Therefore, the total number for this entire program would be,

$\begin{array}{r}\sum _i^n \sum _{j=1}^n 2+\sum _{i=1}^n 1=\sum _{i=1}^n \left(2n\right)+n\\ =n\times 2n+n\left(\because \sum _{j=1}^n 2=2n\right)\\ =2n^2+n\\ =\mathrm{O}\left(n^2\right)\end{array}$

Therefore, the big-O estimate for the number of additions in the segment provided in the algorithm is $O\left(n^2\right)$.