I teach Algorithms at the University of Cambridge. Through this channel I welcome anyone in the world to attend my lectures.
Insertsort takes quadratic time. We can do better. What is the best possible performance achievable by a sorting algorithm? Interestingly, we can work this out a priori. The result we obtain applies to all possible comparison-based sorting algorithms, even ones that haven’t been invented yet.
Since we are looking for the best possible performance but in terms of worst-case analysis, there is a subtle alternation of “best” and “worst” in today’s argument, so make sure not to get them mixed up.
If you like my content, the best way to say thanks is to give it a thumbs up, subscribe to the channel and hit the notification bell to be notified of new videos. Feel free to comment below. I appreciate your feedback.
Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithms/
Course handout:
https://www.cl.cam.ac.uk/teaching/2021/Algorithms/2020-2021-stajano-algs-handout.pdf
My home page:
https://www.cl.cam.ac.uk/~fms27/
Add comment