Suppose the runtime of an algorithm is given by the recurrence T(n) = f(n) + sigma^k _i=1 T(n/b_i) (0 1, n_0, s.t. Forall n > n_0 sigma_i f(n/b_i) greaterthanorequalto then T(n) Element Theta (#leaves) = Theta(n^w). (The runtime is dominated by the work at the leaves of the recursion tree.) (b) If f(n) element Theta(n^w), then T(n) Element Theta(n^w log n). (The work done at each level is approximately equal.) (c) If exist c n_0 sigma_i(n/b_i) lessthanorequalto cf(n), then T(n) Element Theta(f(n)). (Most of the work is done at the root.)