When is ${n \choose k} > (n-k)(k+1) + (n-k-1)k$?

Question

I have two algorithms that output the same result for an input value of a non-negative integer k and a list of n elements, where $1 \leq k \leq n$.

However, the two algorithms are very different in terms of efficiency. One algorithm (call it $X$) uses a binomial approach and requires ${n \choose k}$ time to complete; the other algorithm (call it $Y$) is quadratic and requires $(n-k)(k+1) + (n-k-1)k$ time to complete.

Obviously, when $n$ is large and $k$ is not near the ends, I want to use algorithm $Y$; however, when $k$ is close to 1 or close to $n$, or when $n$ is small, I want to use algorithm $X$.

Right now, I just calculate both numbers, and look at which one is smaller. But this feels like a lot of unnecessary computation. Can you figure out a simpler way to determine when (n Choose k) is smaller?

Answer 1

Never mind, I just figured it out practically from a spreadsheet. I should use Algorithm X when:

• k = 1
• k = n
• k = n-1
• k = 2 and n <= 8
• k = 3 and n <= 5