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.
Usually $n$ is large compared to $k$ and in that case $\binom{n-1}{k-1}$ is approximately $n^{k-1}/(k-1)!$ . The ratio of the two expressions is close to 1.
A procedure that iterates through all subsets of $(k-1)$ distinct elements in an $n$ element set will therefore have time complexity of at least $O(n^{k-1})$, if $k$ is constant, or $O(n^{k-1}/(k-1)!)$ if $k$ is allowed to increase with $n$. The latter looks smaller notationally but is actually larger due to the possibility of an increasing, non-constant power of $n$.