Algorithm Design

When to use

• Analyzing algorithm efficiency and comparing time/space bounds
• Selecting the right paradigm: greedy, divide-and-conquer, DP, or backtracking
• Proving algorithm correctness with loop invariants or induction
• Solving recurrence relations and applying the Master theorem
• Evaluating space-time trade-offs under memory or latency constraints
• Explaining why a greedy choice is (or is not) valid

Core principles

1. Prove before you code — choose a paradigm and establish correctness argument before implementation
2. Tight bounds over loose bounds — Big-Theta tells the truth; Big-O alone can mislead
3. Constants matter at small n — O(n log n) with large constants can lose to O(n²) for n < 10,000
4. Amortized cost is not average cost — a single expensive operation does not break O(1) amortized
5. Greedy requires proof — exchange argument or cut property; intuition is not a proof