DS8001_lec2ex_divideAndConquer.pdf

LECTURE 2: DIVIDE AND CONQUER EXERCISES DS 8001 E X 1: R ECURRENCE C OMPLEXITY C ALCULATIONS □ Solve for the following recurrences (e.g., using guess and check, induction): (a) T(n) = T(n − 5) + c (b) T(n) = T(n/5) + c (c) T(n) = 2T(n/2) + c (d) T(n) = c...

LECTURE 2: DIVIDE AND CONQUER EXERCISES DS 8001 E X 1: R ECURRENCE C OMPLEXITY C ALCULATIONS □ Solve for the following recurrences (e.g., using guess and check, induction): (a) T(n) = T(n − 5) + c (b) T(n) = T(n/5) + c (c) T(n) = 2T(n/2) + c (d) T(n) = cn + T(n/4) + T(3n/4) M Cevik DS 8001 - Divide and Conquer Exercises 2/7 E X 2: R ECURRENCE C OMPLEXITY C ALCULATIONS □ Find the complexity of below functions using recurrence relations (i.e., using T(n) function) def recursiveF1(n,m,o): if n