CS Degree Day 50

Day 50

Half of 100. I will not be finished in 100 days. That became apparent around Day 20. What I am doing is completing the curriculum - taking longer where longer is warranted. The title of the challenge may need revision.

What I did today?

• Lecture 8: Sorting lower bound - Ω(n log n)
• Lecture 9: Linear time sorting - counting sort, radix sort

The proof that comparison-based sorting cannot do better than O(n log n) is fascinating. It is not a proof of what an algorithm does - it is a proof of what any algorithm can do. A ceiling on ingenuity itself.