Maximum Subarray Sum

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations

Lecture Recap

This week you have learned about three things:

The Search and Sorting Problem

You learned how different algorithms for searching and sorting work, understanding their trade-offs. The key insight: preprocessing data (sorting) enables dramatically faster searching ($O(\log n)$ vs. $O(n)$) , and some sorting algorithms are much more efficient ($O(n \log n)$ vs. $O(n^2)$).

Proving What’s Possible (and What’s Not)

We established a theoretical lower bound for the entire class of comparison-based search algorithms. By modeling them as decision trees, we proved that no such algorithm can be faster than $\Omega(\log n)$, making Binary Search asymptotically optimal.

Guaranteeing Correctness with Logic

You learned a powerful, formal technique to prove an iterative algorithm works as intended: the loop invariant. By defining a property and showing it holds at initialization, with each iteration maintenance and at termination, you can rigorously demonstrate correctness.