Session 12: Asymptotics — Big-O from the Definition

Overview

Asymptotic notation stated precisely, with bounds proved from the definition and false bounds disproved by negating it.

Lecturer

Ali Zbeeb (CSE)

Session Information

Core Concepts

  • O, Ω, Θ, o, and ω, written out as quantifier statements (∃c, ∃n₀, ∀n ≥ n₀, …)
  • Proving f = O(g) by exhibiting c and n₀
  • Disproving a bound by negating the definition
  • Common growth classes and their ordering
  • Sums and series as an asymptotics tool: arithmetic, geometric, and harmonic; ∑ 1/i = Θ(log n)
  • Time vs space complexity; worst-case, average-case, and amortized costs
  • Why f = O(g) is considered abuse of notation

Slides

Session 12 Slides: Download PDF

Readings

Exercises & Extra Steps

  • Practice (not collected): prove 3n² + 5n + 2 = Θ(n²) from the definition with explicit constants
  • Practice (not collected): disprove 2^(2n) = O(2ⁿ) by negating the definition
  • Practice (not collected): rank eleven functions by growth rate with a justification for each adjacent pair
  • Problem Set 4 released today — due on paper at the start of S14 (Mon 26 Oct)

Questions? Reach out on the course WhatsApp!