# Test 1 #8 (Version A)

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:=1$
for $i=n$ to $n^2$
$t:= t+2it$

Here there is one loop. In this loop, there are $n^2-n+1$ instances of the value $i$.

For each value of $i$, there is one calculation: $t:= t+2it$. Each such calculation uses three operations: one instance of addition and two instances of multiplication ($(2) \cdot (i) \cdot (j)$).

Therefore, the total number of operations is $3(n^2-n+1)$, which is a quadratic polynomial, so it is $O(n^2)$.

This entry was posted in Test #1 Solutions. Bookmark the permalink.

### 1 Response to Test 1 #8 (Version A)

1. Kate Poirier says:

Most of my comments for #7 work for #8 too.

One difference is counting the number of rounds in the loop (or instances of $i$). In this case, $i$ goes from $n$ to $n^2$. You don’t know what $n$ is so your number of rounds will depend on $n$. You might be tempted to say that there are $n^2-n$ rounds, but you can check that for low values of $n$, this isn’t quite correct. If $n=1$ then there should be one round in the loop, but $n^2-n=1^2-1=0$. If $n=2$ then there should be a round for $i=2, 3, 4$; that is, there should be three rounds, but $n^2-n=2^2-2=4-2=2$. You can see the same pattern for higher values of $n$. You’ll always need to add one to $n^2-n$.