Lower Bounds via Decision Trees

Return to List of Lectures

Previous Lecture

• Misc
  • Exam 2 Date?
    • Nov. 5 (next Thursday)
    • Mostly lower bound arguments, maybe a bit of complexity classes
  • Colloquium
    • “Perpetual Pest Control in the Face of Resistance Evolution?”
    • Dr. John Ringland, University at Buffalo
    • Thursday, Oct. 29, 4:00 PM
    • Newton 202
    • Extra credit
• Questions?
• Lower Bounds via Decision Trees
  • Sorting - Section 8.1
    • Show lower bound for comparison sorting
    • Decision tree based on values less/greater than each other
    • Binary tree
    • Height implies n logn time
      
      • Stirling’s approximation: n! approx. equal √(2πn) (n/e)ⁿ
      • So log(n!) approx. equals log( √(2πn) (n/e)ⁿ )
      • = log√(2πn) + log (n/e)ⁿ
      • = log√(2πn) + n log (n/e)
      • in Θ( nlogn)
    • General result for any sort using comparisons
  • Merging
    
• Next
  • A problem with an exponential lower bound

Next Lecture