SUNY Geneseo Department of Computer Science

Lower Bounds

Previous Lecture

Misc

Learning center closes for Thanksgiving starting Tuesday

Questions?

Optimality

Lower bound (on solution time)

Recall the Towers of Hanoi puzzle

Algorithm to move n disks from pole "source" to pole "dest", via pole "spare"

    solve( n, source, dest, spare )
        if n > 0
            solve( n-1, source, spare, dest )
            move 1 disk from source to dest
            solve( n-1, spare, dest, source )

This runs in Theta(2ⁿ) time

• (Because it does 2ⁿ -1 moves of disks)
• ... which is intolerable

Can you find a faster algorithm?

• Get it down to one recursion, maybe w/ variable to store result of first recursion
• But recursions here produce side effects, not values that can be saved

How could you answer this rigorously?

• Proof
• Design new algorithm, prove that it is correct, analyze for asymptotic time, compare to old
  • Suppose new algorithm is faster
    • This strategy works to prove that prior algorithm is not optimal
  • Suppose new algorithm is not faster
    • This does not prove that old algorithm is optimal
• So analyze the problem instead of individual algorithms
• Look at problem's rules, pre- & postconditions, instead of steps

What can you deduce the algorithm must do, given rules of puzzle

Has to move all n disks

• Rule: only move 1 disk at a time
• So... must use at least n moves

Rule: large disks can't be on small

• So... after moving top 2 disks, one of them has to move again,
• i.e.,... n-1 disks must move more than once

Bottom disk has to move at least once

Other n-1 disks must be off source pole and stacked in tower on 3rd pole

How did the n-1 disks get into tower on 3rd pole?

• Effectively an n-1 disk tower moved

There must some best algorithm for moving towers

Black box algorithm can't be better than best algorithm, can't use fewer moves to move n-1 disk tower than best algorithm would use

Let B(n) be the number of moves the the best algorithm uses to move an n disk tower

Black box algorithm must use at least B(n-1) moves to move n-1 disks to 3rd pole

So black box algorithm uses at least

• B(n-1)
• + 1

After biggest disk moves to destination for the last time, an n-1 disk tower has to move onto its top

• Takes at least B(n-1) moves

So black box algorithm uses at least

• B(n-1) (to clear bigggest disk)
• + 1 (to move biggest)
• + B(n-1) (to put n-1 smaller disks on destination)

This reasoning applies to the best algorithm

• B(n) >= 1 + 2B(n-1) if n > 1
• B(n) >= 1 if n = 1

Closed form

B(n) >= 2ⁿ - 1

Mini-assignment: prove above closed form

Next

Read Section 16.3 (open problems)

Next Lecture