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 lenth:the other: n .
2 2
– 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 n items in the
worst case. Note: T(1) = 0, T(2) = 1
0 if n =1
T(n) =
T +T +Θ( n ifn >1
• Now what???
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).
1 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:
k
–Assume n = 2 . Then:
T(n) < cn + 2T(n/2) < cn + 2{cn/2 + 2T(n/4)}
< 2cn + 4T(n/4) = ... (continuing)
i i
< icn + 2 T(n/2 ) (in general)
< kcn + n T(1) (when i is finally k)
▯ T(n) ∈ O(n log n) (since k = log n).
2 A More Thorough Analysis
• Write it as
0 if n =1
T(n) ≤
T (n/2 +T ) n/2 +an if n )1
• Prove T(n) < cn log n by 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.)
T n ≤T 2 +T 2+an
≤ c log +c log +an
≤ c log +c logn +n
≤ c (logn− 1+ c logn+an
n
= cnlogn−c + an
n 1 c c
≤ cnlogn−c − +an = cnlogn+a − n+
2 2 2 2
≤ cnlogn for, say, 4a
3 Divide-and-Conquer
• A general algorithmic paradigm (strategy)
– Divide:
• Separate a problem into subproblems.
– Conquer:
• Solve the subproblems (recursively).
– Combine:
• Use subproblem results to derive a final result for the
original problem
• Examples: binary search, quick sort, merge sort
When can we use D&C?
• Candidates for D&C:
– Original problem is easily decomposable into
subproblems.
• We do not want to see “overlap” in the subproblems.
– Combining solutions is not too costly.
– Subproblems are about the same size.
– We will see some examples of D&C with special
emphasis on the analysis of execution time.
4 Multiplication of Large Integers
• We illustrate this problem with decimal
digits.
– An actual implementatio

More
Less