SUNY Geneseo Department of Computer Science

Execution Time of Bubble Sort, Part 2

Previous Lecture

Misc

Second hour exam is next Friday (April 1)

• Lists, their algorithms and analyses, related structures
• Rules and format similar to first exam

Questions?

Algorithm Design and Analysis Example

Deriving worst-case execution time for bubble sort

Had two recurrence relations

• Worst-case list messages for findSmallestAndPutAtFront
  • f(n) = 3 if n <= 1
  • f(n) = 10 + f(n-1) if n > 1
  • With closed form f(n) = 10n - 7
• With this, second recurrence gives worst-case list messages for sort
  • s(n) = 1 if n = 0
  • s(n) = 10n - 5 + s(n-1) if n > 0

Mini-assignment: look for pattern, and phrase in English

Patttern:

• 10 * (sum from 1 to n) - 5n + 1
• = 10 n (n+1) / 2 - 5n + 1
• = (10n² + 10n)/2 - 5n + 1
• = 5n² + 5n - 5n + 1
• or 5n² + 1

Prove s(n) = 5n² + 1 by induction on n

• Base case, n = 1
  • s(1) = 6 f/ recurrence
  • = 5 1² + 1
• Induction hypothesis s(k-1) = 5(k-1)² + 1 for some k-1 >= 1
• Show s(k) = 5k² + 1
  • s(k) = 10k - 5 + s(k-1) f/ recurrence
  • = 10k - 5 + 5(k-1)² + 1 by induction hyp
  • = 10k - 5 + 5(k²-2k+1) + 1
  • = 10k - 5 + 5k² - 10k + 5 + 1
  • = 5k² + 1

= Θ(n²)

Next

Stacks, a list-like structure

Motivation: a model for how recursion works (and how it's really implemented in computers)

• Fibonacci numbers (each Fibonacci number is the sum of the 2 previous ones, e.g., F(0) = F(1) = 1; F(2) = F(1)+F(0) = 1+1 = 2; F(3) = F(2) + F(1) = 2 + 1 = 3; etc)

    1:  fib( n )
    2:      if n <= 1
    3:          return 1
    4:      else
    5:          prev1 = fib( n - 1 )
    6:          prev2 = fib( n - 2 )
    7:          return prev1 + prev2

• To execute this, need to keep track of parameter, locals (prev1 and prev2), and return point for each call. So....
  • [Stack of cups to keep track of parameters, locals, etc. in evaluating fib(4)]

Read Section 12.2

Next Lecture