Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
(1) $O(n^{k-1})$ (2) This is just the complexity of finding the minimum of a set, no? –  anon Aug 23 '11 at 3:08

1 Answer 1

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

share|improve this answer
    
Thanks. Can I say that time complexity is exponential. If so, the time complexity of finding the best of W functions is also exponential...? –  samarasa Aug 23 '11 at 3:18
    
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. –  zyx Aug 23 '11 at 3:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.