Consider the following algorithm to compute binomial coefficients. function C(n,

Question

Consider the following algorithm to compute binomial coefficients. function C(n, k) if k = 0 or k = n then return 1 else return C{n - 1, k- 1)+C(n - 1, k) Analyse the time taken by this algorithm under the (unreasonable) assumption that the addition C(n-1, f -1)+C(n-1, k) can be carried out in constant time once both C(n - 1, k - 1) and C(n - 1, k) have been obtained recursively. Let t (n) denote the worst time that a call on C(n, k) may take for all possible values of k, 0 lessthanorequalto k lessthanorequalto n. Express t(n) in the simplest possible form in Theta notation.

Explanation / Answer

Recurrence relation for Binomial Coefficient is given by

t(n,k) = t(n-1, k-1) + t(n-1, k) with t(n,0) = t(n,n) = 0

As we can see that value of n is decreasing by 1 in each and every step. If we ignore k for a moment then at each step problem is getting doubled. So, it leads to t(n,k) = O(2^n).

In worst case, value of k will be n/2. And it will take n/2 steps to reach at 0 or n reaches to n/2. So, by using Stirling's approximation, we have

t(n, n/2) = (2^n)/(sqrt(n))

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.