2
$\begingroup$

I have two questions:

1) How can I represent $\binom{n-1}{k-1}$ in Big $O$ notation.

2) Say $W = \binom{n-1}{k-1}$. Let us consider there are $W$ functions ($f$) to optimize a variable $X$ and say $f_1(X) = p_1$, $f_2(X)=p_2$. What is the time complexity to find the best function among the $W$, i.e. the function that gives the smallest $p$ value?

I think that one simple idea to find an answer for the second question is to sort the $p$ values and retrieve the function corresponding to the smallest $p$ value. Therefore, I think that the answer for the second question is $N\log N$? I am not sure though.

Could you please help me to get this. Thank you.

  • 1
    (1) $O(n^{k-1})$ (2) This is just the complexity of finding the minimum of a set, no?2011-08-23

1 Answers 1