SUNY Geneseo Department of Computer Science

Introduction to Recurrence Relations

Return to List of Lectures

Misc

Problem set 6 due today

Releasing my solution to Lab 3

• Available via our "Exercises" Web page by the time you read this

Questions?

Problem set 6, "amplify", can give one answer to question 2 parts A and B

Recurrence Relations

Section 7.2.1

• How math expressions can be changed into recursive algorithms
• Two cases
  • Base case
  • Recursive case
• Closed forms vs recursive forms
• Can find closed form from proof of recursive form (?)
  • Evaluating recurrence and looking for pattern
  • And then proving that pattern holds
  • Proof is of closed form

Example

• Find a closed form for the recurrence
  • f(n) = 1 if n = 0
  • f(n) = 6 + f(n-1) if n > 0
• Values
  • f(0) = 1
  • f(1) = 6 + f(0) = 6 + 1 = 7
  • f(2) = 6 + f(1) = 6 + 7 = 13 = 6 + 6 + 1 = 2*6 + 1
• f(n) = 6n + 1?
• Prove f(n) as defined by recurrence = 6n + 1
  • By induction on n
  • Base case, n = 0
    • 6 * 0 + 1 = 0 + 1 = 1 = f(0) from 1st line of definition
  • Induction hypothesis
    • Assume f(k-1) = 6(k-1) + 1, k-1 >= 0
  • Show f(k) = 6k + 1
    • f(k) = 6 + f(k-1) by definition
    • = 6 + 6(k-1) + 1 by induction hypothesis
    • = 6 + 6k - 6 +1
    • = 6k + 1

Another example

• Find a closed form for the recurrence
  • g(n) = 3 if n = 0
  • g(n) = 2 g(n-1) if n > 0
• Look at some cases
  • g(0) = 3
  • g(1) = 6 = 2 * 3
  • g(2) = 12 = 2 * 2 * 3
  • g(3) = 24 = 2 * 2 * 2 * 3
• Each g value is twice the one before, g(n) = 2^{something related to n}
  • = 3 * 2ⁿ?
• Prove
  • Base case, g(0) = 3 = 3*1 = 3*2⁰
  • Assume g(k-1) = 3 * 2^k-1
  • Show g(k) = 3 * 2^k
    • g(k) = 2 g(k-1)
    • = 2 * 3 * 2^k-1
    • = 3 * 2^k

A more complicated example

• Find a closed form for the recurrence
  • h(n) = 0 if n = 0
  • h(n) = 0 if n = 1
  • h(n) = 1 + h(n-2) if n > 1
• h(n) = floor( n/2 ) ?
• Prove this a mini-assignment

Hand out problem set 7

Next

Applying recurrence relations to algorithms

Read section 7.2.2