SUNY Geneseo Department of Computer Science

Performance of List Algorithms

Previous Lecture

Questions?

Server for "Course Materials" is really perotine.cs.geneseo.edu

From Windows, try

• Start -> Run
• \\perotine

Lists as Data Sets

    class DataList extends List {

        DataList insert( Object x ) {
            return new DataList( x, this )
        }

        boolean search( Object x ) {
            if ( ! this.isEmpty() ) {
                if ( this.first().equals(x) ) {
                    return true
                }
                else {
                    return this.rest().search( x )
                }
            }
            else {
                return false;
            }
        }

        DataList delete ( Object x ) {
            // Postcondition: Result contains no
            // occurrences of x
            if ( this.isEmpty() ) {
                return this
            }
            else {
                if ( this.first().equals(x) )
                    return this.rest().delete( x )
                else {
                    return new DataList( this.first(), this.rest().delete( x ) )
                }
            }
        }
    }

Efficiency -- how many primitive List messages do these send? (correlated with execution time)

Mini-assignment: work out number of primitive messages for delete

• Recurrence relation
  • f(n) = 1 if n = 0 (isEmpty)
  • f(n) = 5 + f(n-1) if n > 0 (isEmpty, first, constructor, first, rest)
• Closed form
  • f(0) = 1
  • f(1) = 5 + f(0) = 5 + 1
  • f(2) = 5 + f(1) = 5 + 5 + 1
  • f(3) = 5 + f(2) = 5 + 5 + 5 + 1
  • looks like f(n) = 5n + 1
• Proof:
  • Base case, n = 0
    • f(0) = 1
    • = 5 * 0 + 1
  • Induction hypothesis: assume that for natural number n-1 >= 0, f(n-1) = 5(n-1) + 1
  • Show f(n) = 5n + 1
    • f(n) = 5 + f(n-1) [recurrence]
    • = 5 + 5(n-1) + 1 [induction hypothesis]
    • = 5 + 5n - 5 + 1
    • = 5n + 1

Observation:

• Recurrences of the form
  • f(n) = c if n = 0
  • f(n) = k + f(n-1) if n > 0
• Where k and c are constants
• Have closed form f(n) = kn + c
• You can prove this

Best case in terms of length of list

• 1?
• Best/worst brings in other quantities/issues that influence time
  • Worst case is every item not equal to x
  • Best is every item equals x
• Recurrence
  • f(n) = 1 if n = 0
  • f(n) = 3 + f(n-1) if n > 0
• Closed form: f(n) = 3n + 1
  • (kn+c form)

Search

• In terms of length of list, n
• Best case
  • First item equals x
  • f(n) = 2
• Worst case
  • x not in list
  • Recurrence
    • f(n) = 3 + f(n-1) if n > 0
    • f(n) = 1 if n = 0
  • Closed form: f(n) = 3n + 1

Insert:

• Best case: f(n) = 1
• Worst case: f(n) = 1

What can you say about time?

• Time is proportional to 3n+1, 5n+1
  • Really useful thing to say is "about proportional to n"
  • Theta(n)
• Time is proportional to 1, 2

Asymptotic Notation

• Read Sections 9.2.2, 9.2.3
• But just glance over the "Formal Definition" subsection in 9.2.2

Next Lecture