SUNY Geneseo Department of Computer Science

Recurrence Relations and Algorithms, Part 2

Previous Lecture

Questions?

Recurrence Analysis of Recursive Algorithms

How many times does this execute its "if n == 0" test?

    isOdd( n )
        if n == 0
            return false
        if n == 1
            return true
        else
            return isOdd( n-2 )

• Recurrence
  • f(n) = 1 if n = 0 or n = 1
  • f(n) = 1 + f(n-2) if n > 1
• f(n) = floor(n/2) + 1 ?
• Prove this by induction on n
  • Base case 1, n = 0
    • f(0) = floor(0/2) + 1 ?
    • f(0) = 1 from recurrence
    • = 0 + 1
    • = floor(0/2) + 1
  • Base case 2, n = 1
    • f(1) = 1
    • = 0 + 1
    • = floor(1/2) + 1
  • Induction hypothesis
    • f(k-2) = floor( (k-2)/2 ) + 1 for some k-2 >= 0
  • Show f(k) = floor(k/2) + 1
    • f(k) = 1 + f(k-2)
    • = 1 + floor( (k-2)/2 ) + 1
    • = 1 + floor( (k-2)/2 + 1)
    • = 1 + floor( (k-2)/2 + 2/2)
    • = 1 + floor( k/2)

How many "X's" does this print?

    busyPrint( n )
        if n == 0
            print "X"
        else
            busyPrint( n - 1 )
            busyPrint( n - 1 )
            busyPrint( n - 1 )

• x(n) = 3ⁿ?
• Prove this
  • Base case, n = 0
    • x(n) = 1 because "if" succeeds so algorithm executes just "print X"
    • 1 = 3⁰
  • Induction hypothesis: busyPrint(n-1) prints 3^n-1 x's for some n >= 0
  • Show busyPrint(n) prints 3ⁿ x's
    • n > 0 so "if" test fails
    • Algorithm executes "else"
    • 3 calls on busyPrint(n-1)
    • each prints 3^n-1 x's
    • So total x's is 3 (3^n-1) = 3¹ 3^n-1 = 3ⁿ.
• What if you didn't see the 3ⁿ right away?
  • Recurrence relation
    • x(n) = 1 if n = 0
    • x(n) = 3 x(n-1) if n > 0

• Aha! x(n) = 3ⁿ ?
• Proof by induction on n
  • Base case, n = 0
    • x(0) = 1 from recurrence
    • = 3⁰ algebra
  • Induction hypothesis: x(k-1) = 3^k-1 for k-1 >=0
  • Show x(k) = 3^k
    • x(k) = 3 x(k-1) from recurrence
    • = 3 (3^k-1) induction hypothesis
    • = 3^k algebra

How many times does the towers of Hanoi algorithm move a disk?

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

• Recurrence
  • m(n) = 0 if n = 0
  • m(n) = 1 + 2m(n-1) if n > 0
• m(n) = 2ⁿ - 1 (from pages 236 - 238 of book)

Next

Rest of this week: Prof. Zollo does an extended example of design and analysis of recursion

Next week: A notation for relating concrete operation counts to general execution time

Read Section 9.2

Next Lecture