CODEWITHSUNDEEP
algorithmrecursiontime-complexityrecursive-datastructures
Giackkk
Giackkk

Reputation: 121

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

Upvotes: 1

Views: 178

Answers (2)

user1196549
user1196549

Reputation:

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.

Upvotes: 2

Gassa
Gassa

Reputation: 8874

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.

Upvotes: 1

Related Questions