Class Notes (1,100,000)
CA (630,000)
UW (20,000)
CS (1,000)
CS341 (20)
Lecture

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

Department
Computer Science
Course Code
CS341
Professor
Forbes Burkowski

This preview shows pages 1-2. to view the full 8 pages of the document. 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).

Only pages 1-2 are available for preview. Some parts have been intentionally blurred. 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 to view full version

Only pages 1-2 are available for preview. Some parts have been intentionally blurred. 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
 
= + − +
 
 
≤ =