In the previous few entries we’ve been discussing quick_sort and analyzing the run-time complexity of recursive algorithms. We’re going to apply what we’ve learned so far to finding the median of an array in O(n) time. Then we’re going to see how that can be added to quick_sort to guarantee that it finishes in O(nlog_2(n)) time.
In the previous entry (Sorting, Random Permutations, and little bit of Probability), we introduced quick_sort, gave a version of it in C++ and started to analyze how many steps it takes to sort a vector of floating point numbers. In this entry, we continue that analysis and prove some results that will help us get a feel for other recursive algorithms.
This entry starts out by building to Zassenhaus’ Lemma, and finishes by proving the Jordan-Holder theorem about subnormal sequences for finite groups. Enjoy!
In this article we mostly talk about partial orders, and lattices, which are a special type of partial order. We tie it in with our discussions of subgroups before proving two distribution laws for lattices.
