CS341 Study Guide - Final Guide: Quickselect, Artery Recordings, Selection Sort

• School: University of Waterloo
• Department: Computer Science
• Course: CS341
• Professor: Flora Ng

Document Summary

(1) if n > 1 if n = 1. T (n) = which we can solve to nd. Stoogesort: def stoogesort(a[1n]): if n <= 1: return if a[1] > a[2]: swap(a[1], a[2]) stoogesort(a[1\frac{2n}{3}]) stoogesort(a[\frac{n}{3}+1n]) stoogesort(a[1\frac{2n}{3}]) Let t (n) be the runtime of stoogesort on n elements. 3 if n > 1 if n = 1. The master theorem: let t (n) = at ( n. ) + f (n) if n > n + 0 and c if n = n0. Set d = logb ai and pick a small constant > 0. Case 1: f (n) = o(nd ) = t (n) = (nd). Case 2: f (n) = (nd) = t (n) = (nd log n). 3: limn f (n)/nd+ = = t (n) = (f (n)): substitution method: guess the form of the solution t (n) x), then verify your guess by induction and ll in any constants.