SUNY Geneseo Department of Computer Science

Recurrence Relations and Algorithms, Part 1

Previous Lecture

Questions?

Recurrence Relations and Algorithms

Section 7.2.2

Recursive algorithms can be converted into equations (recurrence relations)

Equations let us figure out how many steps algorithm executes as function of some number, n

Question: example that counts test in an "if"?

• Factorial
• This was analyzing "arithmetic operations" an algorithm executes
• i.e., *, -, and > which happens to be executed in the test

For Example....

How many times does this send a "substring" message?

    countSpaces( String str )
        if str == ""
            return 0
        else if str.charAt(0) == ' '
            return 1 + countSpaces( str.substring(1) )
        else
            return countSpaces( str.substring(1) )

• Recurrence on length of string, n
  • f(n) = 0 if n = 0
  • f(n) = 1 + f(n-1) if n > 0
• Closed form
  • f(n) = n
  • "kn + c" recurrence
    • If f(0) = c; f(n>0) = k + f(n-1)
    • Then closed form is always kn + c
  • k = 1, c = 0, here

How many primitive robot messages does this send, as a function of the robot's distance from the wall?

    // In some subclass of Robot...
    lineToWall()
        if this.okToMove()
            this.paint( green )
            this.move()
            this.lineToWall()
            this.move()
        else
            this.turnLeft()
            this.turnLeft()

• Recurrence (n = distance to wall)
  • f(n) = 3 (turnLefts & okToMove) if n = 0
  • f(n) = 4 + f(n-1) if n > 0
    • (paint and 2 moves & okToMove)
• Using kn + c, closed form is f(n) = 4n + 3

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
• Patterns

• So f(n) = floor(n/2) + 1 ?
  • e.g., floor(1/2) = 0
  • floor(2/2) = 1
• Prove this by induction on n
  • Base cases
    • 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
      • ...
  • Induction hypothesis: f(k-2) = floor( (k-2)/2 ) + 1 for some k-2 >= 0
  • Show f(k) = floor(k/2) + 1
    • ...
• Mini-assignment: Complete the "..." parts of the above proof

Next Lecture