CS 1501 Lecture Notes - Lecture 2: Binary Search Tree, Merge Sort, Linear Search
8 Sep 2016
School
Department
Course
Professor
Document Summary
Cs 1501 9/7/16: all logs are base 2 but you need not write because log bas 2 of n = (log(n)/log(2)) which makes the base 2 a multiplicative constant. Insertion sort (n^2) good for mostly sorted data. Quicksort for data not mostly sorted; fast; with a good pivot don"t use if looking for stable sort nlogn in worse case n^2; sorting in place. Merge sort if you want stability; always nlogn; requires more memory. To sort 1,000,000 32 bit integer = 4mb-->if mostly sorted insertion sort. 1 tb of numbers consider external sorting; writing to disk. **merging all chunks together at once means fewer reads/writes but more disk seeks. When interviewing ask about data type, amount, and organization(mostly ordered or not?) Brute-force or exhaustive search run time is bounded by number of potential solutions. Example: pin cracking tree will have 10^n different pins 4 # pins give 10^4 possibles.
