COMPSCI 61B Lecture Notes - Lecture 35: Quicksort, Sorting Algorithm, Binary Tree

• School: Berkeley
• Department: Computer Science
• Course: COMPSCI 61B
• Professor: Joshua Hug

Document Summary

Can be used to solve other tasks, sometimes in non-trivial ways. Improves duplicate nding from a naive n2 to n log n. Sorting improves 3sum from a naive n3 to n2. Asymptotically, n log(n) and log(n!) are basically the same (grow at the same rate) asymptotically. We have shown several sorts to require theta(n log n) worst case time. Let the ultimate comparison sort (tucs) be the asymptotically fastest possible comparison sorting algorithm, possibly yet to be discovered, and let r(n) be its worst case runtime in theta notation. By comparison sort, we mean that the sort uses the compareto method in java to make decisions. Worst case run-time of tucs, r(n) is o(n log n). Worst case run-time of tucs, r(n) is omega(n) Have to at least look at every item. We can make an even stronger statement on the lower bound, omega(n log n)