Question

could anyone help with these questions?

1. Find the general solution to each of the following recurrence relations (a) an+2 7ant1 +12an 2 (b) an+2 - 7an+1 +12a, -n22 (c) an+12an 2. To calculate the computational complerity_a measure for the maximal possible number of steps needed in a computation of the mergesort' algorithm (an algorithm for sorting natural numbers in non-decreasing order) one can proceed by solving the following recurrence relation: n -2 an-12" -1, with ao0 (a) Use the method of generating functions to solve this recurrence relation (b) The relation between the number tm of computations needed to sort m numbers, and the solution am of the recurrence relation, is given by t2m-am. Use this to find an expression for tn, where n -2" (or log2 n- m), explicitly as a function of n, and conclude that tn ~n log2 n for large n.

Answer 1

(a) Given recurrence relation a_n + 1 - 7a_n + 1 + 12a_n = 2^n Auxiliary equation m^2 - 7m + 12 = 0 m^2 - 4m - 3m + 12 = 0 m (m - 4) - 3 (m - 4) = 0 (m - 3) (m - 4) = 0 m = 3, m = 4 complementary function (a_n_c) = c_1 (3)^n + c_2 (4)^n particular integral a_n)_p = A.2^n Therefore A 2^n + 2 - 7A 2^n + 1 + 12A 2^n = 2^n 4A - 14A + 12A = 1 16A - 14A = 1 2A = 1 A = 1/2 Therefore General solution is a_n = c_1 (3)^n + c_2 (4)^n + 1/2 2^n (b) Given Recurrence relation: a_n + 2 - 7a_n + 1 + 12a_n = n^2 2^n (1) complementary function is as same in (a) PI (a_n)p = (A + Bn + Cn^2) 2^n
$\p Consicler he can Co have Multipl ina by χη and un 1-2, 1- 月$

Answer 2

(a) Given recurrence relation a_n + 1 - 7a_n + 1 + 12a_n = 2^n Auxiliary equation m^2 - 7m + 12 = 0 m^2 - 4m - 3m + 12 = 0 m (m - 4) - 3 (m - 4) = 0 (m - 3) (m - 4) = 0 m = 3, m = 4 complementary function (a_n_c) = c_1 (3)^n + c_2 (4)^n particular integral a_n)_p = A.2^n Therefore A 2^n + 2 - 7A 2^n + 1 + 12A 2^n = 2^n 4A - 14A + 12A = 1 16A - 14A = 1 2A = 1 A = 1/2 Therefore General solution is a_n = c_1 (3)^n + c_2 (4)^n + 1/2 2^n (b) Given Recurrence relation: a_n + 2 - 7a_n + 1 + 12a_n = n^2 2^n (1) complementary function is as same in (a) PI (a_n)p = (A + Bn + Cn^2) 2^n