CS 106B Lecture Notes - Lecture 12: Merge Sort, Insertion Sort, Sorting Algorithm
21 Oct 2016
School
Department
Course
Professor
Document Summary
Logistics: there will be a midterm review, tba, midterm materials will come out next week (old exams, study guides, etc. , comments on hw 3. Serpinski triangle should throw a string exception. )f your program throws an exception and you don"t. Recursive fibonacci function has exponential handle it, the program crashes computational complexity because each performs two additional recursions, but that is not the case for every recursion. For finding n factorial, only one more recursive call for each additional n, so it is only o(n) When adding (cid:883) + (cid:884) + . Sorting: sorting consists of putting elements into a particular order, comparison sorts at best have a complexity of o(n log n, also need to consider the space complexity. Some sorts can be done in place, meaning the sorting does not take extra memory. Important factor when choosing a sorting algorithm: there are stable and unstable sorts.
