SUNY Geneseo Department of Computer Science

Recurrence Relations and Recursive Algorithms

Return to List of Lectures

Misc

Problem set 7 due today

My solution to Lab 3 is on Web (see "Exercises" page for links to its pieces)

Faculty applicant (Suprakash Datta) interviewing Monday

• Student roundtable 11:30 - 12:00, Fraser 208
• Research talk (sensor networks) 2:30, Milne 213
• Model class (Internet congestion control), 4:30, Welles 123

Questions?

Mini-Assignment

Prove that h(n) = floor( n/2 ) is 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

Induction

• Base case
  • n = 0. h(0) = 0 = floor(0/2)
  • n = 1. h(1) = 0 = floor(1/2)
• Assume h(k-2) = floor( (k-2)/2 ) for k-2 >= 0
• Show h(k) = floor( k/2 )
  • h(k) = 1 + h(k-2)
  • = 1 + floor( (k-2)/2 )
  • = 1 + floor( k/2 - 2/2 )
  • = 1 + floor( k/2 - 1 )
  • = floor( k/2 ) but beware pulling terms out of "floor"

Recurrence Relations and Algorithms

Section 7.2.2

• Same kind of steps as earlier
  • Make function to count steps/operations from recursive algorithm with recursive part and base case ...
    • Constants added together in recurrence correspond to single steps in algorithm
    • Recursive terms in recurrence correspond to recursion in algorithm
  • Find & prove closed form
• Doable with algorithms that don't return anything and that return values
• Recurrences and execution time
  • Count some or all steps algorithm executes, execution time proportional to closed form

Example

• An algorithm that finds a factor of x less than or equal to n given precondition n >= 1

        factor( x, n )
            if n <= 1
                return 1
            else if x % n == 0
                return n
            else
                return factor( x, n-1 )

• In the worst case, how many arithmetic operations (%, ==, <=, -) does this perform?
• A(n) = # of arithmetic operations
  • A(n) = 1 if n <= 1
  • A(n) = 4 + A(n-1) if n > 1
• A(n) = 4(n-1) + 1 ?
• Proof
  • Base case, n = 1
    • A(1) = 4 * (1-1) + 1 = 4*0 + 1 = 1
  • Assume A(k-1) = 4(k-2) + 1, k-1 >= 1
  • Show A(k) = 4(k-1) + 1
    • A(k) = 4 + A(k-1) by definition
    • = 4 + 4(k-2) + 1
    • = 4(k-1) + 1

Next

Abstracting operation counts and time

Read sections 9.2.1 and 9.2.2