time complexity recursive function

Question

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

If this function intends to calculate the Binomial Coefficient, then it is wrong. It does not work well once n < k. — trincot
– trincot, Commented Jul 11, 2022 at 11:59
Perhaps a fix would be if (k=0) or (k=n) then return(1) -- or is it a trick question altogether? — Gassa
– Gassa, Commented Jul 11, 2022 at 12:54
@trincot: it computes B(n-1, n+k-1)=B(k, n+k-1) for n≥1, k≥0 and is always right. — user1196549
– user1196549, Commented Jul 11, 2022 at 13:52
@YvesDaoust But, for example, B(2, 5) = B(1, 5) + B(1, 4) = 2. That's clearly wrong. Although when we start with 0<=k<=n, the base looks misplaced but perhaps indeed provides the right answer, just following a different path to 1s on the border?.. — Gassa
– Gassa, Commented Jul 11, 2022 at 14:58
Just checked -- it's wrong, really -- assuming the goal was to compute binomial coefficients. Unless I made a mistake in Python translation: ideone.com/hQJ6s4 . For example, B(4, 2) is 7 instead of 6. — Gassa
– Gassa, Commented Jul 11, 2022 at 15:04

score 2 · Accepted Answer · 2022-07-11 13:47:29Z

2

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.

edited Jul 11, 2022 at 13:47

answered Jul 11, 2022 at 13:15

user1196549

Sign up to request clarification or add additional context in comments.

6 Comments

Gassa Over a year ago

I don't really understand what B is. For example, T(4,2) = T(3,2) + T(3,1) = [T(2,2) + T(2,1)] + [T(2,1) + T(2,0)] = {T(1,2) + T(1,1)} + {T(1,1) + T(1,0)} + {T(1,1) + T(1,0)} + 1 = 7. By the formula in the answer, T(4,2) = B(3,5) = B(2,5) -- but I fail to see what's B then.

Gassa Over a year ago

If B(k,n) is just the common choose(n,k), then I'm sure it's wrong: choose(5,2) = choose(5,3) = 5! / 2! / 3! = 120 / 2 / 6 = 10, which is not equal to 7.

user1196549 Over a year ago

@Gassa: you still misread the formula. Pay attention.

Gassa Over a year ago

Alright, either please kindly tell me what my error is, or let's drop it altogether. I'm quite okay with being wrong on the internet.

user1196549 Over a year ago

@Gassa: B(k, n-1+k) != B(n, k).

|

Gassa · Accepted Answer · 2022-07-11 12:45:43Z

1

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.

answered Jul 11, 2022 at 12:45

Gassa

8,9173 gold badges34 silver badges52 bronze badges

2 Comments

Gassa Over a year ago

I second @trincot's comment about the function not working as intended right now, but still want to assume that it's not a trick question and will be fixed, and so focus this answer on the particular approach to analyzing the complexity.

user1196549 Over a year ago

No, trincot is making a wrong assumption. The function does compute binomial coefficients faithfully, but not in the way he thinks.

Collectives™ on Stack Overflow

time complexity recursive function

2 Answers 2

6 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related