Show (n choose k-1) * n^O(1) time complexity

[Isak Lyckberg]

Show (n choose k-1) * n^O(1) time complexity as suggested by Andreas in commit b89d6cf.

[Isak Lyckberg]

Idea: For algorithm L, first change the inequality (7) to something like this, then use the same argument of bounding the size of the recursion tree to get (n choose k)n^O(1). Perhaps is there a literature reference to the bound?

[Isak Lyckberg]

Or, if we use that k <=n/2, we have that $\sum_{i=0}^{k-1} (n \choose i) \leq k * (n \choose k-1)$, since binomial coefficients are increasing over the interval 0<k<n/2. Thus algorithm L runs in time < k(n choose k-1)n. Thoughts?

[Isak Lyckberg]

Should be resolved in new commit.