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$
-
$\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– David D2017年10月17日 19:08:46 +00:00Commented Oct 17, 2017 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– Raphael2017年10月17日 20:30:06 +00:00Commented Oct 17, 2017 at 20:30
3 Answers 3
The only way that your algorithm can compute ${n \choose k}$ is by adding ${n \choose k}$ 1's together.
Now prove it.
-
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– gnasher7292017年10月14日 00:06:08 +00:00Commented Oct 14, 2017 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– user786422017年10月14日 02:10:19 +00:00Commented Oct 14, 2017 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$2017年10月14日 02:28:38 +00:00Commented Oct 14, 2017 at 2:28
-
$\begingroup$ It returns 1 $\binom{n}k$ times. $\endgroup$user78642– user786422017年10月14日 04:21:39 +00:00Commented Oct 14, 2017 at 4:21
-
$\begingroup$ And how many addition operations does it perform? $\endgroup$2017年10月14日 23:07:49 +00:00Commented Oct 14, 2017 at 23:07
Since at each recursive call the number of calls gets doubled so the complexity would be $O(2^{n})$.
-
$\begingroup$ This is a somewhat pessimistic bound unless $k$ is very close to $n/2$. $\endgroup$Yuval Filmus– Yuval Filmus2017年10月13日 12:10:13 +00:00Commented Oct 13, 2017 at 12:10
-
$\begingroup$ but @kyrio asked for worst case complexity. So isn't it correct? $\endgroup$srd091– srd0912017年10月13日 12:18:38 +00:00Commented Oct 13, 2017 at 12:18
-
$\begingroup$ The OP mentions "however we have to take k into account." $\endgroup$Yuval Filmus– Yuval Filmus2017年10月13日 12:27:20 +00:00Commented Oct 13, 2017 at 12:27
-
$\begingroup$ @YuvalFilmus Sorry, missed that totally. $\endgroup$srd091– srd0912017年10月13日 12:31:39 +00:00Commented Oct 13, 2017 at 12:31
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.
-
$\begingroup$ Thanks for the edit. I'm not sure how to go from one relation to the other, though. $\endgroup$user78642– user786422017年10月13日 17:32:53 +00:00Commented Oct 13, 2017 at 17:32
-
$\begingroup$ You have to do some of the work yourself. I won't do your homework for you. $\endgroup$Yuval Filmus– Yuval Filmus2017年10月13日 17:36:41 +00:00Commented Oct 13, 2017 at 17:36
-
$\begingroup$ Of course, I didn't ask you to ;) $\endgroup$user78642– user786422017年10月13日 19:23:42 +00:00Commented Oct 13, 2017 at 19:23