Question

Give a big-O estimate for the number additions used in this segment of an algorithm.

Answer 1

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.