CS136 Study Guide - Range Tree, Priority Queue, Quicksort
Document Summary
Midterm questions: multiple choice answers: c, c, b, a, b, b, a, a, b, b, a, b, b, b, b, recurrence, priority queues, quicksort, radixsort, avl trees, 2-3 trees, b-trees, range searching. Find the asymptotic order of 3n + log n. 3n + log n 4n for all n > 0, so 3n + log n o(n). Find the asymptotic order of(cid:80)n (cid:17) n(cid:88) (cid:16) 1 n(cid:88) xi ) for x > 1. (cid:16) 1 i=1( 1 (cid:17)i xi i=1 x i=1 (cid:16) 1 n(cid:88) (cid:16) 1 n 1(cid:88) i=1 x (cid:17)i 1 (cid:17)i x i=0. Answer: (cid:80)n xi ) (1). i=1( 1 i=1( 1 xi ) = 1 x + + 1. 1 (cid:16) 1 n(cid:88) x , a constant, so(cid:80)n xi xi ) (1). (cid:17) o(1) i=1 i=1( 1 a constant, so. Leaves in an avl tree can be in levels which di er by more than 1. Consider the following avl (with balance elds shown):
