Header Image
Creative Commons image courtesy of Flickr user StormPetrel1-
Recent Posts
Recent Comments
- In the Spotlight: MAT2540 – Discrete Structures and Algorithms II – The Open Road on Links
- OpenLab Workshop for Opening Gateways Fellows | 2018-2019 Opening Gateways Faculty Seminar on Final Exam Review
- Eric on Eric’s Final Review
- Kate Poirier on Hints/reminders from today’s class
- Kate Poirier on Final Exam Review
Archives
Categories
Meta
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
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 
times (not 
) since there’s a round for 
. Each round involves one comparison 
and one comparison 
. 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 
.