algorithm_analysis.md

Algorithm analysis

Table of contents

• Complexity analysis
  • Amortized analysis
• Loop invariants
  • Binary search

---

Complexity analysis

Amortized analysis

🔗

• Lecture 21: Amortized analysis – Cornell University CS 3110: Data structures and functional programming (2012)
• Amortized complexity in layman’s terms? – Stack Overflow
• Difference between average case and amortized analysis – Stack Overflow

Loop invariants

A loop invariant is a property of a program loop that is true before and after each iteration.

🔗

• Loop invariant – Wikipedia

📖

• Col.4: Writing correct programs – J.Bentley, Programming pearls (1999)

📄

• J.Bentley. Programming pearls: Writing correct programs – Communications of the ACM 26, 1040 (1983)
• D.Gries. A note on a standard strategy for developing loop invariants and loops – Science of Computer Programming 2, 207 (1982)

Binary search

🔗

• Invariants for binary search. Part I, Part II, Part III, Part IV, Part V, Part VI, Part VII, Part VIII, Part IX, Part X – Dr.Dobb’s Journal