CS 3510 Midterm: CS 3510 GT t1Practice
Document Summary
Test 1 in class, friday, sep 8, 2016: main topics. Solving recurrences using master theorem (other methods are optional). Applications of fast multiplication: not included: Details of how to multiply numbers faster than n2. Guess and check / recursion tree: master theorem works for everything on test: proving big-o bounds (homework 1, problem 1. If f1 = o(g1(n)), f2 = o(g2(n)), then. For any constants a, b, and c, o(loga(n)) o(nb) o(cn), Ln(n) = (log n) = (log2 n) = (logc n): divide-and-conquer and setting up running time recurrences (homework 1, problems 2 and 3. Make a recursive calls to problems of size n/b. T (n): running time when given input of size n. If total cost of split/combine is o(nd), runtime recurrence is: T (n) = at (n/b) + o(nd): master theorem: T (n) = a t (cid:18) n b(cid:19) + c nd,
