SUNY Geneseo Department of Computer Science

Practice with Recurrence Relations

Previous Lecture

Misc

First hour exam next Tuesday, March 2

• Covers material since start of course
• (Object oriented abstraction, Proof, Experiments, Conditionals, Recursion, Induction, Recurrences)
• Whole class period
• 4 - 5 short-answer questions
• Open book, open notes, open computer
• Closed person
• Sample Exam on the Web

Questions?

Timing worst case in lab: n = 25

• n = length of array section

Counting "elses" in analyzing algorithms?

• e.g., thereAndBack
• It's the actions in the test that are being counted

Recurrence Relations

Section 7.2.2

Building a "bridge" between algorithm and recurrence function

Make functions for number of times algorithm executes something from algorithm

• e.g., takeJourney

Steps

• Make recurrence for function
• Find closed form of function by looking for pattern
• Prove via induction (like in lab)

Same approach for implicit parameters

Can also use recurrence relations to determine abstract execution time

• Real time is proportional to recurrence function
• e.g., powerOfTwo is really inefficient

Recurrences become more useful as algorithms get more complicated

Practice with Recurrences

Here's an algorithm to move a robot n tiles forward, then bring it back to where it started, facing in its original direction. How many primitive robot messages (i.e., messages defined for Robot) does it send?

    // In some subclass of Robot...
    void forwardAndBack( int n ) {
        if ( n > 0 ) {
            this.move();
            this.forwardAndBack( n-1 );
            this.turnLeft();
            this.turnLeft();
            this.move();
            this.turnLeft();
            this.turnLeft();
        }
    } 

• Recurrence (warning: the following isn't really a recurrence relation)
  • M(n) = 5n + n
  • Base case, n = 1
    • Move 1
    • Recursion, does nothing
    • 5 more messages
    • = 6 messages total
  • n = 2
    • Move 1
    • Recursion (n=1)
    • 6 messages
    • 5 more messages
    • = 12 messages
  • Generalize pattern to n + 5n
• Or (preceding required detailed tracing of algorithm, it wasn't a recurrence relation. Truly using recurrence relations simplifies a lot of algorithmic details that aren't really relevant to how many steps the algorithm executes)
  • f(n) = 6 messages sent directly
    • + f(n-1) from recursion
    • if n > 0
  • f(n) = 0 if n = 0
• Plug values in for n, look for pattern
  • f(0) = 0
  • f(1) = 6 + f(0) = 6
  • f(2) = 6 + f(1) = 6 + 6
  • f(3) = 6 + f(2) = ...
• Or work from n down
  • f(n) = 6 + f(n-1)
  • = 6 + (6 + f(n-2))
  • = 6 + (6 + (6 + f(n-3)))
• Looks like f(n) = 6n
• Prove that recurrence and "6n" are the same function
  • Base case, n = 0
    • f(0) = 0 from recurrence
    • = 6 * 0
  • Induction
    • Assume f(k-1) = 6(k-1)
    • Prove f(k) = 6k
      • Since k-1 >= 0, k > 0
      • So f(k) = 6 + f(k-1) from recurrence
      • = 6 + 6(k-1)
      • = 6k

This algorithm computes the sum of the even numbers from n down to 2, given the preconditions that n is even and n >= 2:

    int sumEvens( int n ) {
        if ( n == 2 ) {
            return 2;
        }
        else {
            return n + sumEvens( n - 2 );
        }
    }

• How many arithmetic operations does this execute?
• Recurrence
  • f(n) = 1 if n = 2
  • f(n) = 3 + f(n-2) if n > 2
• Patttern spotting
  • f(2) = 1
  • f(4)= 3 + f(2) = 3 + 1
  • f(6) = 3 + f(4) = 3 + 3 + 1
  • f(8) = 3 + f(6) = 3 + 3 + 3 + 1
• # of 3's looks like (n/2 - 1)
  • Plus 1
• Suggests f(n) = 3(n/2 - 1) + 1
  • = (3n-4)/2
• f(n) = (3n-4)/2
• Prove this closed form equivalent to recurrence as a mini-assignment

Next Lecture