COS 226 Midterm: COS 226 Princeton Midterm Spring 12 Solution
31 Jan 2019
School
Department
Course
Professor
Document Summary
E min height of a binary heap with n keys. E max height of a binary heap with n keys. C min height of a 2-3 tree with n keys. E max height of a 2-3 tree with n keys. E min height of left-leaning red-black bst with n keys. F max height of left-leaning red-black bst with n keys. A min height of a weighted quick union tree with n items: 1, 1. 2 lg n: log3 n, ln n, lg n, 2 lg n, 2 ln n. E max height of a weighted quick union tree with n items: n (b) insertion sort and top-down mergesort are parsimonious. The keys b and c get compared twice, once in rst iteration and once in second iteration. When the array is full: worst case: 8n. When the array is one-quarter full. operation description time charat(int i) return the ith character in sequence.
