COEN 179 Lecture Notes - Lecture 24: Binary Tree, Merge Sort
6 Jun 2020
School
Department
Course
Professor
Document Summary
2)decision trees: works only for restricted class of comparison-based algorithms. which can only compare or assign input values. "bye: a binary tree of height h has at most 2^h leaves. Teg n7 so a binary tree with m leaves must have height at least. In other words, the corresponding comparison-based algorithm must make at least. A c teg rt) comparisons on some input. Corollary: any comparison-based algorithm for sorting must make at least. =d ( neg n) comparisons on some input . Tap n(cid:15482) a b c a c b a c c a c a b c b a. Outcome b c a corresponds to input abc ca. Outcomes, so the height of any binary tree corresponds to a comparison-based algorithm must be. Con: this is a tight bound due to running time of merge sort/ heap sort. If we are allowed more than comparisons, there are o(n lg n) sorting algorithms.
