Search code examples
algorithmrecursiontime-complexityrecursive-datastructures

time complexity recursive function

How can i calculate the time complexity and the t(n) equation of this recursive function?

Function CoeffBin(n,k)
if (n=1) or (k=0) then return(1)
else return (CoeffBin(n-1,k) + CoeffBin(n-1,k-1))
Solution

  • Let T(n, k) be the cost function and assume a unit cost of the statement if (n=1) or (k=0) then return(1).

    Now neglecting the cost of addition, we have the recurrence

    T(n, k) =
    1 if n = 1 or k = 0 (that is T(1, k) = T(n, 0) = 1)
    T(n-1, k) + T(n-1, k-1) otherwise

    The solution is T(n, k)=B(n-1, n-1+k)=B(k, n-1+k) where B denotes Binomial numbers and the costs also follows Pascal's triangle !

    For a more precise estimate, we can assume the costs a when n=1or k=0, and T(n-1,k)+T(n-1,k-1)+b otherwise. The solution is then (a+b)B(k, n+k-1)-b.