1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Take a look at this too. $\endgroup$
    – Ben Longo
    Dec 15, 2015 at 4:06

1 Answer 1

0
$\begingroup$

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
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .