York University

• EECS 3101

• Average running time Recursion Tree Functions Master Theorem -Height logb n -bottom row: n logb a Sorting -Insertion sort and selection sort : worst case O(n2 ) -Merge sort and heap sort: worst case O(n log n) Quicksort -Worst case: O(n2 ) -proof: show T(n) = O(n2 ), then T(n) = Ω(n2 ), then T(n) = Θ(n2 ) -average case: O(n log n) Lower bound for sorting -worst case: O(n log n) – upper bound, Ω(n log n) -lower bound -sorting with assumptions: O(n): counting sort - bucket sort: time you spend on each bucket X number of buckets (using insertion sort O(n2 )): average case: O(n + n2 /k + k) -stability in sorting: insertion sort, bucket sort, merge sort (all stable); heap sort and quick sort (not stable) - Decision Tree: leaf node is a possible sorted order, n! possible orders for n elements, number of leaves L >= n!, has at most 2h leaves, 2 h >= n! -> h >= log(n!) -> Ω(n log n) – h represents the worst-case number of comparisons to sort -To determine maximum -> need at least n-1 comparisons -Proving lower bound using reduction: using another harder problem’s known lower bound Binary Heap Tree -nearly complete: height O(log n) -> worst case -Insert(Q, x): bubble-up -worst case O(log n) -ExtractMax(Q): switch root and last node – bubble down (with elder child) – worst case O(log n) -IncreasePriority(Q, x, k): worst case O(log n) -HeapSort: 1) swap first and last 2) decrement heap size 3) bubble down swapped node 4) repeat – O(n log n) – sorts an unsorted array in place -BuildMaxHeap(A): converts an unsorted array into a heap in placestart index floor(n/2) and go to 1 – from bottom up – bubble down root and move up – runtime O(n) – bubble down is O(log n) Dynamic Programming -two conditions: 1) overlapping subproblems 2) problem has optimal substructure -two methods: 1) memoization: user recursion and remember answers of subproblems to use again. 2) Bottom-up: solve subproblems first (put them in array) and access them later -step1: Define subproblem -step2: Find recursive relation between subproblem solutions, and verify problem has optimal substructure, and identify base case -step3: implement using bottom