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. t : = 0 for i : = 1to3 for j : = 1to4 t : = t + ij

Question

Mathematics

Vincent Ortega

18 December, 18:49

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. t : = 0 for i : = 1to3 for j : = 1to4 t : = t + ij

+4

Answers (1)

Know the Answer?

Jefferson Harrison · Answer 1

We have a "rectangular" double loop, meaning that both loops go to completion.

So there are 3*4=12 executions of t:=t+ij.

Assuming two operatiions per execution of the innermost loop, (i. e. ignoring the implied additions in increment of subscripts), we have 12*2=24 operations in all.

Here the number of operations ( + or * ) is exactly known (=24).

Big-O estimates are used for cases with a varying scale of operations, governed by a variable (usually n) to indicate the sensitivity of the number of operations relative to a change in the size of n.

Here we do not have a scale, nor n is defined. The number of operations is constant and known at 24. So a variable is required to find the big-O estimate.