01:198:344 Lecture Notes - Lecture 2: Binary Search Algorithm

• School: Rutgers University
• Department: Computer Science
• Course: 01:198:344
• Professor: Farach- Colton

Document Summary

Last lecture: example of binary search, max. How to model an algorithm and get worst case running times (maxin ta(in). Function f = o(g) if there exists constants c and n0 such that for all n n0, f (n) cg(n). Function f = o(g) if there exists constants c and n0 such that for all n n0, f (n) < cg(n) or lim n f (n) g(n) Figure out such de nitions for , pages 47-51, clrs, 3rd edition. We have f (n) = (g(n)) if and only if f (n) = o(g(n)) and g(n) = o(f (n)), or f (n) = (g(n)) Some examples of algebra with o, o, etc. Sort n, 2log n, log log n, n10, log(n! Examples: finding max, t (n) = t (n 1) + 1; binary search. T (n) = t (n 1) + 1. T (n 1) = t (n 2) + 1. T (1) = 1 (1) (2) (3) (4) (5) (6)