194k views
4 votes
Give a big-O estimate for the number additions used in this segment of an algorithm.

t := 0
for i := 1 to n
for j := 1 to n
t := t + i + j
I understand the answer is O(n^2) but how?

User Milsyobtaf
by
7.3k points

1 Answer

6 votes
big-O notation is a way to describe a function that represents the n amount of times a program/function needs to be executed.

(I'm assuming that := is a typo and you mean just =, by the way)

In your case, you have two loops, nested within each other, and both loop to n (inclusive, meaning, that you loop for when i or j is equal to n), and both loops iterate by 1 each loop.

This means that both loops will therefore execute an n amount of times. Now, if the loops were NOT nested, our big-O would be O(2n), because 2 loops would run an n amount of times.

HOWEVER, since the j-loop is nested within i-loop, the j-loop executes every time the i-loop ITERATES.

As previously mentioned, for every i-loop, there would be an n amount of executions. So if the i-loop is called an n amount of times by the j loop (which executes n times), the big-O notation would be O(n*n), or O(n^2).

(tl;dr) In basic, it is O(n^2) because the loops are nested, meaning that the i-loop would be called n times, and for each iteration, it would call the j-loop n times, resulting in n*n runs.

A way to verify this is to write and test program the above. I sometimes find it easier to wrap my head around concepts after testing them myself.
User Alfina
by
7.1k points