CISC 121 Lecture Notes - Lecture 34: Binary Search Algorithm, Merge Sort
10 Apr 2019
School
Department
Course
Professor
CISC 121 verified notes
34/38View all
Document Summary
This week we"ll look at a couple of sorting algorithms that employ recursion instead of nested-loop iteration to do their work. These sorts can be implemented iteratively (i. e. non-recursively), but the recursive definitions of them are much easier to code and, unlike last week"s recursive algorithms, are quite practical. The time complexity of these recursive sorts is either o(n log n) in all circumstances or o(n log n) in most circumstances. You"ll recall that the time complexity of binary search is o(log n). That makes the big-o time complexity of these recursive sorts equal to the big-o time complexity of this code snippet. We can see from this excel chart comparing the growths of t(log n), t(n) (linear), t(n log n), and t(n2), that while not as good as linear, t(n log n) (in grey) is a great improvement over t(n2) (yellow).
