CS Degree Day 29

Made up for yesterday. Studied from 11pm to 4am. There is a particular quality to late-night studying. The world contracts to the desk and the screen.

What I did today?

6.1000 - wrapping up:

• Computational complexity: O(1), O(log n), O(n), O(n²)
• Searching and sorting: linear search, bisection search, bubble sort, selection sort, merge sort
• Wrote exam paper - scored 88/100

The merge sort analysis is elegant. The recurrence relation T(n) = 2T(n/2) + O(n) resolving to O(n log n) is satisfying in the way that mathematical truths sometimes are - you follow the steps and at the end something inevitable appears.