1 Complexity and Recurrences Match each one of the following six recursive formulas with one of the possible six solutions (i.e., just label each solution with the letter of its formula; no explanations needed): n! log2 n 2n n log2 (a) T(1-2; T(n) = 2T(n-1). (b) T(1) = 0; T(n)-2T(n/2) + n. (e) T(1)-1; T(n) 4T(n/2) (d) T(1) = 0; T(n) = T(n/2) + 1. (e) T(1) = 1; T(n) = nT(n-1). (f) T(1) = 0; T(n) = T(n-1) + 2. The recursive definitions are for n 2 2. When the recursion is for T(n/2) you may assume that n is a power of 2 2 Recursion Trees For each recurrence above, give the branching factor, shrinking factor f (f it erists), dominant weight location (write root, leaves, or all levels), and heigh t of its recursion tree, no explanations needed. (Recall that a tree's branching factor is the number of children each non-leaf node has.,) # children c shrinking factor f weight location height