23-Recurrences

# 23-Recurrences - 6/15/2011 Analysis of Merge-Sort CS/ENGRD...

This preview shows pages 1–2. Sign up to view the full content.

6/15/2011 1 CS/ENGRD 2110 Object-Oriented Programming and Data Structures Spring 2011 Thorsten Joachims Lecture 23: Recurrences Analysis of Merge-Sort Recurrence describing computation time: T(n) = c + d + e + f + 2 T(n/2) + g n + h recurrence T(1) = i base case How do we solve this recurrence? 2 public static Comparable[] mergeSort(Comparable[] A, int low, int high) { if (low < high) { //at least 2 elements? cost = c int mid = (low + high)/2; cost = d Comparable[] A1 = mergeSort(A, low, mid); cost = T(n/2) + e Comparable[] A2 = mergeSort(A, mid+1, high); cost = T(n/2) + f return merge(A1,A2); cost = g n + h } .... cost = i Analysis of Merge-Sort Recurrence: T(n) = c + d + e + f + 2 T(n/2) + g n + h T(1) = i First, simplify by dropping lower-order terms and replacing constants by their max T(n) = 2 T(n/2) + a n T(1) = b Simplify even more. Consider only the number of comparisons. T(n) = 2 T(n/2) + n T(1) = 0 How do we find the solution? 3 Solving Recurrences Unfortunately, solving recurrences is like solving differential equations No general technique works for all recurrences Luckily, can get by with a few common patterns You learn some more techniques in CS2800 4 Analysis of Merge-Sort Recurrence for number of comparisons of MergeSort T(n) = 2T(n/2) + n T(1) = 0 T(2) = 2 To show: T(n) is O(n log(n)) for n 2 {2,4,8,16,32,…} Restrict to powers of two to keep algebra simpler Proof: use induction on n 2 {2,4,8,16,32,…} Show P(n) = {T(n) c n log(n)} for some fixed constant c . Base: P(2) T(2) = 2 c 2 log(2) using c=1 Strong inductive hypothesis: P(m) = {T(m) c m log(m)} is true for all m 2 {2,4,8,16,32,…,k} . Induction step: P(2) A P(4) A A P(k) P(2k) T(2k) 2T(2k/2) + (2k) 2(c k log(k)) + (2k) c (2k) log(k) + c (2k) = c (2k) (log(k) + 1) = c (2k) log(2k) for c 1 5 Solving Recurrences Recurrences are important when using divide & conquer to design an algorithm Solution techniques:

This preview has intentionally blurred sections. Sign up to view the full version.

View Full Document
This is the end of the preview. Sign up to access the rest of the document.

## This note was uploaded on 09/05/2011 for the course CS 211 at Cornell University (Engineering School).

### Page1 / 4

23-Recurrences - 6/15/2011 Analysis of Merge-Sort CS/ENGRD...

This preview shows document pages 1 - 2. Sign up to view the full document.

View Full Document
Ask a homework question - tutors are online
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}