SUNY Geneseo Department of Computer Science

Lower Bounds

Previous Lecture

Misc

I'm out of town tomorrow and Friday

• Prof. Zollo lectures Friday

Questions?

Text input with buffered reader?

• Looked at a Sample Program that reads and prints a text file line by line

Limits of Computing

Is there a faster algorithm for solving the Towers of Hanoi?

Sections 16.1 and 16.2

• Asymptotic relations for problems rather than specific algorithms
• Lower bound = asymptotic expression that is fastest possible solution, least possible execution time
• Algorithm is optimal if its asymptotic running time is lower bound
• 16.2 - Towers of Hanoi
  • Define function M(n) for number of disks that have to be moved to solve n-disk problem based on problem's rules via recurrence that reflects limits of problem
    • M(n) = 1 if n = 1
    • M(n) >= M(n-1) + M(n-1) + 1 if n > 1
  • Closed form is M(n) = 2ⁿ - 1, which is lower bound for Towers of Hanoi
  • Also running time for standard algorithm, so it was optimal
  • Lower bounds for searching and sorting
    • Searching: lower bound is Θ(logn)
    • Sorting: lower bound is Θ(n logn )

Other Lower Bound Examples

• Determine whether a set of n items has a member satisfying some property (e.g., does the set contain anything green)
• Adversaries control set
• Searchers only ask to see 1 item at a time
• Both teams know the property
• Both teams know n
• Try it
  • n = 5
  • Property = "is it a toy"
  • Questions: ////
• By choosing the set as questions are asked, adversaries can force n questions

Next

Open problems

Read Section 16.3

Next Lecture