time complexity recursive function-CodePudding

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))

CodePudding user response：

Note that, at the base level (that is, when not doing recursive calls), the function always returns ones.

So, to have an answer of X, the program will ultimately need to do X-1 additions, and thus do X calls executing the case in the first line and X-1 calls executing the second line.

So, whatever the intended result of the function call is -- perhaps choose(n,k), -- if you prove that it works, you automatically establish that the number of calls is proportional to that result.

CodePudding user response：

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.