SUNY Geneseo Department of Computer Science

Recurrence Relations for Analyzing Algorithms, Part 2

Previous Lecture

Questions?

Reading Summary

Finish reading Section 7.2.2

Expands on recurrence relations

More examples

More complex algorithms & their recurrences

Value-producing recursion

• Recurrence relation should include return step
  • (because analysis counted arithmetic operations (*, -), there were some in the return statement)
  • return n * factorial(n-1)
• Otherwise recurrence is similar to others

Execution time and 2-to-the-n example

• Not all recurrences have linear closed forms
• "Running time" depends on program, language, computer, etc.
  • But operation counts can give you something that is proportional to time

Mini-Assignment

How many lines of output from

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

Is it 2n?

f() = number of "hello world" messages manyMessages prints for a given parameter

• f(n) = 0 if n = 0
• f(n) = 1 + 2f(n-1) if n > 0

Closed form? f(n) = n

No, f(2) doesn't work

Previous similar recurrences had closed forms of the form 2ⁿ - 1

Prove f(n) = 2ⁿ - 1 by induction on n

• Base case, n = 0
  • f(0) = 0 [definition]
  • = 1 - 1 = 2⁰ - 1
• Induction step
  • Assume f(k-1) = 2^k-1 - 1
  • Show that "it works" for k, i.e., f(k) = 2^k - 1
    • f(k) = 1 + 2f(k-1) [recurrence]
    • = 1 + 2*(2^k-1 - 1) [induction hypothesis]
    • = 1 + 2*2^k-1 - 2
    • = 2^k - 1

Other Examples

    class ExtendedArray

        private int data[]

        selectionSort( n )
            // put elements 0 .. n into ascending order
            if ( n > 0 )
                int maxPos = findMax( n )
                temp = data[n]
                data[n] = data[maxPos]
                data[maxPos] = temp
                this.selectionSort( n-1 )

        findMax( n )
            // get index of max value in positions 0 .. n
            if ( n > 0 )
                int prev = findLargest( n-1 )
                if ( data[n] > data[prev] )
                    return n
                else
                    return prev
            else
                return 0

Count comparisons in findMax, then plug that result into recurrence for selectionSort

findMax does n comparisons

For selectionSort, let C(n) = # comparisons selectionSort(n) does

• C(n) = 0 if n = 0
• C(n) = n [from findMax] +C(n-1) if n > 0

Next

Applying many of the principles we've seen for algorithm design (e.g., recursion, object-oriented programming, induction, recurrences, experiments) to organizing data for efficient processing

Data structures

Next Lecture