CSE 15 Lecture Notes - Lecture 5: Quicksort, Heapsort, Merge Sort
Document Summary
1/n*log(e)= 0: ex: you have a list of n random numbers, how fast can i do member(x, list)? for(int i = 0; i < len; i++) if (list[i] == x) return i; return -1; o(n) If we know x is in the list, then . 5n. Idea 1: sort it o(nlog(n): ex: take set of 10 numbers; to find 7, you divide 10 by 2, then check to see if the number you"re looking for is larger. If so, search remaining upper half. log(2)(n) is the amount of times you can divide the number by two: n = 2^(log(2)(n), o(logn) optimal, if list is sorted, you can find something in logarithmic time. Importance of optimizing your program: done in mathematica program. Intractable too hard to compute: n! = o(n) there are n operations f(k) = f(k-2) + f(k-1) f(5) f(3) f(4) f(1) f(2) f(2) f(3) f(1) f(0) f(1) f(2) f(0) f(1: x3 f(2)s, o(2^k)
