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, k-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 t(n). Express t(n) in the simplest possible form in Theta notation.

Explanation / Answer

Ans:

code:

Example: Recursion tree for n = 5 and k = 2. . For large values of n, there will be many common subproblems.

Time complecity: Binomial coefficients are represented by C(n, k) or (nk) and can be used to represent the coefficients of a binomail

T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)       with        T(n,n) = T(n,0) = O(1)

c(n, k) = sum for upper triangle + sum for the lower rectangle

= C(n-1, k-1) + C(n-1, k) for n > k > 0

= (k-1)k/2 + k(n-k) (nk)

=(n*k)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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