1. Solve the following recurrence equation to get a closed-formula for T(n) using backward substitution. You...

Transcribed Image Text:

1. Solve the following recurrence equation to get a closed-formula for T(n) using backward substitution. You may assume that n is a power of 2. T(n) = 1 if n=1 = 4T +n if n: fn > 2 2 2. Consider the following recursive algorithm. ALGORITHM Q(n) //Input: A positive integer n If n = 1, return 1' else return Q(n - 1) + 2 x n 1 a) Set up a recurrence relation for the function's values and solve it to determine what this algorithm computes. b) Set up a recurrence relation for the number of multiplications made by this algorithm and solve it. c) Set up a recurrence relation for the number of additions and substractions made by this algorithm and solve it. 3. Solve the following recurrence equations using the Master Theorem. (a) T(n) 16T (n/4)+n4 (b) T(n) (c) T(n) = 125T (n/5)+3logn = 64T(n/8) + n 1. Solve the following recurrence equation to get a closed-formula for T(n) using backward substitution. You may assume that n is a power of 2. T(n) = 1 if n=1 = 4T +n if n: fn > 2 2 2. Consider the following recursive algorithm. ALGORITHM Q(n) //Input: A positive integer n If n = 1, return 1' else return Q(n - 1) + 2 x n 1 a) Set up a recurrence relation for the function's values and solve it to determine what this algorithm computes. b) Set up a recurrence relation for the number of multiplications made by this algorithm and solve it. c) Set up a recurrence relation for the number of additions and substractions made by this algorithm and solve it. 3. Solve the following recurrence equations using the Master Theorem. (a) T(n) 16T (n/4)+n4 (b) T(n) (c) T(n) = 125T (n/5)+3logn = 64T(n/8) + n