Give a big-o estimate for the number additions used in this segment of an algorithmi:=0, for i:=1 to n, for j: = 1 to n, t:=t+i+j

Question

Mathematics

Grizzly

19 June, 08:31

Give a big-o estimate for the number additions used in this segment of an algorithmi:=0, for i:=1 to n, for j: = 1 to n, t:=t+i+j

+5

Answers (1)

Know the Answer?

Andreas Leblanc · Answer 1

We have a "square" double loop, meaning that both loops go to completion at n.

So there are n^2 executions of t:=t+i+j.

Assuming two additions per execution of the innermost loop, (i. e. ignoring the implied additions in increment of subscripts), we have 2n^2 additions in all.

Therefore the given code section is of O (n^2), i. e. the highest power (if polynomial) and ignore coefficients.