-----------------------------------------------------------------------------
COMP 731 - Data Struc & Algorithms - Lecture 6 - Tuesday, July 4, 2000
-----------------------------------------------------------------------------
Today: Mergesort
Divide-and-conquer and divide-and-conquer recurrences
* Mergesort some cards
Algorithm Mergesort (A, l, r)
if r <= l then return
p = \lfloor (l+r)/2 \rfloor
Mergesort (A, l, p)
Mergesort (A, p+1, r)
Merge (A, l, p, r)
Describe Merge ....
Let T(n) = # of comparisons spent by Mergesort
to sort an array A of size n, **in the worst case**
*Construct a best-case example for Merge
*Construct a worst-case example for Merge
Recurrence:
/ T(\lfloor n/2\rfloor) + T(\lceil n/2 \rceil) + n-1 if n>=2
T(n) = |
\ 0 if n <= 1
*Make a table of T(n) values, n=1..10
Thesis: in all "natural" recurrences, we can drop floors and ceiling,
additive and multiplicative factors in added terms, and we will not change
the \Theta-behavior. (Can prove for specific examples, but won't here.)
Can also omit specifying exact base case, with convention "for sufficiently
small n, the value is \Theta(1)." Again, it is the "thesis" that this
won't matter for natural recurrence relations, if we only want to know the
answer to within \Theta.
Here: we'd just consider
T(n) = 2T(n/2) + n
** Solve this by substitution method
** Then solve the recurrence T(n) = 3T(n/2) + n // giving Theta(n^\lg_2 3)
(note: this will give rise to wanting to evaluate
1 + x + x^2 + ... + x^k, which is Theta(x^k). Show how to get
an exact solution by algebraic manipulation.)
(note: remind students of properties of logs, log_a b = log_c b / log_c a, so,
in particular, 3^log_2 n = n^log_2 3 )
** Then solve the recurrence T(n) = 2T(n/2) + n^2 // giving Theta(n^2)
General divide-and-conquer paradigm
\ n / a subproblems
\-----------------/
/ / \
/ / \
n/b n/b ... n/b
| | |
| | | Gives rise to: T(n) = aT(n/b) + f(n)
\|/ \|/ \|/
y_1 y_2 y_a
\ \ /
\ \ / f(n) time for recombining
\ \ ... /
answer