Test#1 Review-Jose Betance


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

1 Response to Test#1 Review-Jose Betance

  1. Kate Poirier says:

    This is a very clear explanation, Jose, but there’s an error with how you’ve set it up. Certainly, this algorithm has the same complexity as the one we saw in class that finds the maximum in a set of n integers. In that example, we included comparisons that told us whether we had reached the end of the while loop or not, but we separated those from the number of comparisons of elements of the list we’d have to perform. The loop runs n-1 times (not 2n-1) since there’s a round for i=2, 3, \dots, n. Each round involves one comparison min > a_i and one comparison i \leq n. So your answer is NOT ignoring the comparisons used to determine whether the end of a loop has been reached. When you ignore these comparisons, the answer will just be n-1.

Leave a Reply

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