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.

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

Leave a Reply

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