# Test #1 Review – Brian Gil

Section 3.3 = #3

Give a big-θ estimate for the number of operations of this algorithm:

m := 0

for i := 1 to n

for j := i +1 to n

m := max(aiaj, m)

The values of i and j:

i := 1 <= n        →     n (rounds)

j := i + 1 <= n   →    n – 1 (rounds)

i := n + 1 <= n  →   1 (Ends loop)

j := n + 1 <= n  →   1 (Ends loop)

n(n – 1) + 1 + 1 = n^2 – n + 2

Exactly n^2 – n + 2 comparisons are used whenever this algorithm is applied. Hence, the algorithm has time complexity θ(n^2).

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

### 1 Response to Test #1 Review – Brian Gil

1. Kate Poirier says:

Hi Brian. There’s an error in your calculation of the number of $j$ loops. Notice that $j$ goes from $i +1$ to $n$, not from $1$ to $n$. Therefore, for different values of $i$ there are different numbers of possible values of $j$. For example, if $i = 1$ then $j$ can be $2, 3, \dots, n$, so there are $n-1$ values of $j$. But if $i = 5$ then $j$ can be $6, 7, \dots, n$, there are only $n-5$ values of $j$. In particular, the $j$ loops are getting shorter as $i$ gets higher. It might be easier to check the number of values of $j$ for each individual value of $i$, and then add them all up. Hint: your complexity is correct but your exact number of comparisons isn’t.