CS234 Lecture Notes - Lecture 13: Quicksort, Merge Sort
7 Jun 2015
School
Department
Course
Professor
Document Summary
Overall: enqueue is dequeue is (n^2) (1) => total (n) => total (n) (n^2: pq is a sorted array (insertion sort) Overall: switched: pq is a heap (heap sort) (n^2) (similar to above but enqueue & dequeue (n log n) enqueue is dequeue is (n) total (using bottom up sorting) (log n) => total. Let a = len(l) and b = len(m: wc when largest and second largest are in different lists, iterate (a+b) times, repeatedly appending a+b things onto [] takes (a+b) time (linear time to repeatedly append) (a+b) overall. Mergesort tree n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/4 n/4 n/4 n/4 n/2 n/2 one node per call to mergesort nodes labeled with corresponding input size runtime of merge at a node labeled m is (m) runtime of mergesort at a node labeled m (ignoring recursion) is (m) .
