ALGORITHMS Lecture Notes - Erik Demaine, Search Algorithm, Binary Tree
Document Summary
Instructors: erik demaine, jason ku, and justin solomon. Data structure build(x) find(k) insert(x) find min() find prev(k) Sorted array n n log n n log n n n n. 1 n log n delete(k) find max() find next(k: idea! Can we find(k) faster than (log n): answer is no (lower bound)! (but actually, yes!?) Comparison model: in this model, assume algorithm can only differentiate items via comparisons, comparable items: black boxes only supporting comparisons between pairs, comparisons are , , =, =6. , outputs are binary: true or false: goal: store a set of n comparable items, support find(k) operation, running time is lower bounded by # comparisons performed, so count comparisons! Yay: more generally, height of tree with (n) leaves and max branching factor b is (logb n, to get faster, need an operation that allows super-constant (1) branching factor. Direct access array: exploit word-ram o(1) time random access indexing!
