Introduction to Lower Bound Arguments

Return to List of Lectures

Previous Lecture

• Misc
  • Colloquium
    • “The Group Menagerie”
    • Dr. Elizabeth Wilcox, SUNY Oswego
    • Today (Thursday), Oct 15, 4:00
    • Newton 202
    • Extra credit for short write-ups, as usual
  • Exam 1
    • Tuesday Oct. 20
    • Time and correctness analysis of algorithms
    • 4 - 6 short-answer questions
    • Open book, notes, computer; closed person
    • Practice problems available through “Exercises” page
• Questions?
• Master Theorem and Algorithms
  • Simple recursive matrix multiplication
    • Recurrence
      • T(1) = 1
      • T(n) = 8 T(n/2) + n², n > 1
    • Master method
      • a = 8, b = 2, f(n) = n²
      • n^log₂8 = n³
      • f(n) = n² = O( n^3-ε) for ε < 1
      • Case 1: T(n) = Θ(n³)
  • Strassen’s algorithm
    • Recurrence
      • T(1) = 1
      • T(n) = 7 T(n/2) + n², n > 1
    • Closed form via master method
      • a = 7, b = 2, f(n) = n²
      • n² in O( n^log₂7-ε ) = O( n^2.???-ε )
      • Case 1, T(n) = Θ(n^2.807…)
• Lower Bounds for Problems
  • Algorithm = procedure for computing a function
  • Problem = function
  • Lower bound = smallest asymptotic worst-case time for any algorithm that solves the problem
  • Examples
    • Matrix multiplication
      • Best time is Θ(n²) because there are n² output values that all have to be written
      • Argument based on input or output sizes
        • Doesn’t give much insight into problem
        • Bounds found this way often aren’t tight, i.e., there’s a gap between bound and what known algorithms actually do
        • i.e., this example shows that lower bound analysis is possible, but the technique isn’t very satisfying / useful
    • Minimum in sorted (ascending order) list
      
      • This is a case where an output-based lower bound is tight
      • Also illustrates how you might not have to look at all the inputs to solve a problem
    • Minimum in unsorted list
      • Example of adversary argument
      • Adversary strategy: always give smaller value for i^th query than any value given for previous queries
      • So you need n queries
      • Thus optimal time in Θ(n)
• Next
  • Optimal time for searching a sorted list
  • Mini-assignment: try to come up with an adversary argument and optimal time

Next Lecture