1
$\begingroup$

Here's a naïve algorithm that computes $ \binom{n}k $ (or "n choose k"), with either $k=0$ or $1\le k \le n$:

def coefficient(n, k):
    if k == 0 or k == n:
        return 1
    return coefficient(n-1, k-1) + coefficient(n-1, k)

Now the time complexity has to be bounded by $2^n$, however we have to take $k$ into account. The best cases are when k = 0 or k = n. So, with k and n decrementing, we get the most branching when $k = \frac{n}2$.

I'm looking for the worst case time complexity. I can write the recurrence relation, but I don't know how to go from here:

$T(n,k) = T(n-1, k-1) + T(n-1, k) + constant$

Improve this question
$\endgroup$
2
  • $\begingroup$ I am working on the exact same problem. Have you find a way to resolve the reccurence relation ? I think the final answer is O(2^n) or O(2^(n+1)). $\endgroup$ – David D Oct 17 '17 at 19:08
  • $\begingroup$ Welcome to Computer Science! Let me direct you towards our reference questions which cover some relevant fundamentals in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael♦ Oct 17 '17 at 20:30
4
$\begingroup$

The only way that your algorithm can compute ${n \choose k}$ is by adding ${n \choose k}$ 1's together.

Now prove it.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ It's like the naive recursion formula for Fibonacci numbers, where the result fib(n) is found by adding fib(n) 1's together. $\endgroup$ – gnasher729 Oct 14 '17 at 0:06
  • $\begingroup$ Indeed, I can see the connection. It's the fact that there are two variables now that is wrinkling my brain :D $\endgroup$ – user78642 Oct 14 '17 at 2:10
  • $\begingroup$ There are exactly two things that this function does: return 1, or add two numbers together. Exactly how many times must it return 1? Exactly how many addition operations must it perform to add these 1's together? $\endgroup$ – Pseudonym Oct 14 '17 at 2:28
  • $\begingroup$ It returns 1 $\binom{n}k$ times. $\endgroup$ – user78642 Oct 14 '17 at 4:21
  • $\begingroup$ And how many addition operations does it perform? $\endgroup$ – Pseudonym Oct 14 '17 at 23:07
1
$\begingroup$

Since at each recursive call the number of calls gets doubled so the complexity would be $O(2^{n})$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is a somewhat pessimistic bound unless $k$ is very close to $n/2$. $\endgroup$ – Yuval Filmus Oct 13 '17 at 12:10
  • $\begingroup$ but @kyrio asked for worst case complexity. So isn't it correct? $\endgroup$ – srd091 Oct 13 '17 at 12:18
  • $\begingroup$ The OP mentions "however we have to take k into account." $\endgroup$ – Yuval Filmus Oct 13 '17 at 12:27
  • $\begingroup$ @YuvalFilmus Sorry, missed that totally. $\endgroup$ – srd091 Oct 13 '17 at 12:31
0
$\begingroup$

Try using the ansatz $T(n,k) = \alpha \binom{n}{k} + \beta$.

Indeed, whenever you are faced with a non-homogeneous recurrence relation, it is a good idea to solve its homogeneous counterpart, which in this case is $$ T(n,k) = T(n-1,k-1) + T(n-1,k). $$ Pascal's identity shows that the binomial coefficients satisfy this recurrence. The extra degrees of freedom included in the ansatz should help deal with the base cases and with the additional constant in the actual recurrence relation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the edit. I'm not sure how to go from one relation to the other, though. $\endgroup$ – user78642 Oct 13 '17 at 17:32
  • $\begingroup$ You have to do some of the work yourself. I won't do your homework for you. $\endgroup$ – Yuval Filmus Oct 13 '17 at 17:36
  • $\begingroup$ Of course, I didn't ask you to ;) $\endgroup$ – user78642 Oct 13 '17 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy