SUNY Geneseo Department of Computer Science

Recurrence Relations for Analyzing Algorithms

Previous Lecture

Misc

Hand out Lab 8

Questions?

Lab 7 - "primitive linedrawing message" = message provided by LineDrawing, e.g.,

• movePen
• setAngle
• getAngle
• setColor
• getColor
• getPositionX
• etc.

Lab 7 due Friday

Recurrence Relations and Algorithms

Read Section 7.2.2 through factorial example (pg. 297)

How recursion works?

Recurrence relation

• Bridge between recursive algorithm and formula for number of steps executed
• Recurence relation parallels algorithm
• Mathematically describes something about the algorithm (e.g., number of steps)
• Two definitions
  • Base case for recurrence
    • Corresponds to algorithm's base case
      • Same parameter values
      • Number of steps algorithm does in its base case
  • Recursive case for recurrence
    • Algorithm's recursive case
    • Number of steps algorithm executes in recursive case
      • Plus recursion to represent number of steps entailed by algorithm's recursion (recurrence has same parameter as recursive call)
    • Same parameter values that cause algorithm to execute recursive arm
• Closed form is final, quicker, easier way to evaluate function defined by recurrence

Implicit parameters

• Way to figure out number of steps, measure algorithm?
• Every recurrence relation has a parameter
• Sometimes recursive algorithm doesn't have an explicit parameter that controls recursion
• In these cases parameter to recurrence is implicit in algorithm's environment

Examples

How many "println" messages in

Algorithm:

    countDown( n )
        if ( n > 1 )
            System.out.println( n ) <- count these
            countDown( n - 1 )

Recurrence:

• P(n) = # of println messages sent when countDown's parameter is n
  • P(n) = 0 if n <= 1 [base case]
  • P(n) = 1 + P(n-1) if n > 1 [recursive case]

Closed Form:

• Look at values

• Or expand P(n) = 1 + P(n-1)
  • = 1 + ( 1 + P(n-2) )
  • = 1 + ( 1 + ( 1 + P(n-3) ))
  • ....
  • = 1 + .... 1 + P(1)
  • = 1 + 1 + ... + 1 + 0

Guess n-1

Prove that P(n) = n -1 by induction on n

• Base case, n = 1.
  • P(1) = 0 [from recurrence relation]
  • = 1-1
• Induction Hypothesis: Assume P(k-1) = (k-1) - 1 for some k-1 >= 1
• Show P(k) = k - 1
  • P(k) = 1 + P(k-1) [from recurrence relation]
  • = 1 + (k-1) - 1 [from induction hypothesis]
  • = k-1 [algebra, cancelling 1 and -1]

Next

Finish applying recurrence relations to algorithm analysis

Mini-Assignment

• How many lines of text does this print?

    manyMessages( int n )
        if ( n > 0 )
            System.out.println( "Hello world" )
            this.manyMessages( n-1 )
            this.manyMessages( n-1 )

• Is it 2n?

Finish reading Section 7.2.2

Next Lecture