CS341 Lecture Notes - Merge Sort, Quicksort, Binary Search Algorithm

28 views8 pages
16 Oct 2011
School
Course
1
Divide and Conquer
• MergeSort
We are given a list of n elements.
Split list into two lists each of length n/2.
More precisely, one with length: the other: .
Sort each list using merge sort (recursive call).
Merge the sorted lists to get the final result.
Merge sort analysis:
Let T(n)= number of comparisons to sort nitems in the
worst case. Note: T(1) = 0, T(2) = 1
Now what???
0 if 1
( )
( ) if 1
2 2
n
T n n n
T T n n
=
=   
   
+ + Θ >
   
   
   
   
2
n
2
n
Floors and Ceilings
In practice, floors and ceilings are often
neglected.
To be mathematically precise, we should not
neglect them.
This can nearly always be done, but details
can get quite messy.
In this
course, we will almost always gloss over
them. This is fine for our purposes, but in other
settings it might not be (e.g. when writing a
formal proof for publication).
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 8 pages and 3 million more documents.

2
Solving Recurrences
Method 1: Recursion Trees
Method 2: Master theorem
Method 3: Guessing and Checking method
We will study these in the next unit. For now,
we solve the recurrence in an ad-hoc fashion.
Simple Merge Sort Analysis
A simple analysis gives us a good guess:
Assume n = 2k. Then:
T(n) < cn + 2T(n/2) < cn + 2{cn/2+ 2T(n/4)}
<2cn + 4T(n/4) = ... (continuing)
< icn + 2iT(n/2i)(in general)
< kcn + n T(1) (when iis finally k)
T(n)
O(nlog n)(since k = log n).
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 8 pages and 3 million more documents.

3
A More Thorough Analysis
Write it as
( ) ( )
0 if 1
( )
/2 / 2 if 1
n
T n
T n T n an n
+ + >
 
 
Prove T(n)< cn log nby induction on n.
Base case: n = 1. True since T(n) = 0.
Inductive step: assume T(k)< ck log k
for k < n,and prove true for k = n.
Mergesort (cont.)
( ) 2 2
log log
2 2 2 2
log log
2 2 2
(log 1) log
2 2
log 2
1
log 2 2
n n
T n T T an
n n n n
c c an
n n n
c c n an
n n
c n c n an
n
cn n c an
n
cn n c an
   
 
+ +
   
 
 
   
       
+ +
       
       
   
+ +
 
   
   
   
− + +
   
   
 
= − +
 
 
 
− +
 
  log
2 2
log for, say, 4
c c
cn n a n
cn n c a
 
= + − +
 
 
≤ =
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 8 pages and 3 million more documents.

Get access

\$10 USD/m
Billed \$120 USD annually
Homework Help
Class Notes
Textbook Notes