Asymptotic Growth (3)

Michael L. Littman

September 9th, 1997

• ANNOUNCEMENTS
  • Updates to Web Pages
• EUCLID'S ALGORITHM
  • Euclid's Algorithm
  • Efficiency Analysis
  • Classic Sequence
  • Rate of Growth of F
  • A Corollary
  • Inverse Fibonacci
  • Fibonacci Meets Euclid
  • Fibonacci Upper Bound
  • Summary
• ASYMPTOTIC GROWTH
  • Comparing Algorithms
  • Asymptotic Growth
  • Example
  • Counterexample
  • Big Theta
  • Examples
  • Base of Logs
  • Complete Set
  • Big O
  • Some Technical Details
  • Applying to Algorithms
  • Math in Big Theta World
  • An Example with Proof
• HOMEWORK
  • Homework 1
  • Homework 2