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

5

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$.

  • 0
    If k is a large enough function of N, such as k=[N/2], then certainly there are exponentially many k-subsets. If an algorithm searches through all of those subsets in the worst case, that will take time exponential in N. Actually if k grows like any positive power of N, this is considered "exponential time" in complexity because it is equivalent to time (constant)^N with respect to polynomial time reductions such as representing the same input originally of length N, in space N^3 or N^20.2011-08-23