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

Explain your answer.

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.

One 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.

Leave a Reply

Your email address will not be published. Required fields are marked *