MCS 401 homework #8 Due date: 19981113 D. J. Bernstein 19981106 There is a program that, for a particular positive real number r, sorts n numbers in time at most T (n), where T (1) = 1 and T (n) = min {n^{2}, T (⌊n/2⌋) + T (⌈n/2⌉) + rn} for n ≥ 2. Exercise 29. Design an algorithm that, given r, computes T (n) for all n ∈ {1, 2, 3, …, L} using O(L) operations. Exercise 30. Design an algorithm that, given r, computes T (n) using O(log n) operations. Exercise 31. Here is a recursive algorithm to print the binomial coefficient \binom{n}{i} if n ≥ i ≥ 0: print 1 if i = 0 or i = n; otherwise compute \binom{n−1}{i} and \binom{n−1}{i−1} recursively, and print the sum \binom{n−1}{i} + \binom{n−1}{i−1}. Give an exact formula for the number of additions performed by this algorithm. Exercise 32. Design an algorithm that computes \binom{n}{i} using O(in) operations.