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 havent done combinations in forever, so I have no idea howto do this...

I have an unknown quantity of items in a set, and I need to figure out how many combinations there are of 35 unique items from that set. I know that the formula for combinations is $\frac{n!}{35!(n-35)!}$... but I need to express this as a polynomial for time complexity of an algorithm. is this doable?


To elaborate a bit on this:

I have to design an algorithm to show that a 35-Clique can be solved in polynomial time (k-clique is an exponential time complexity)... but knowing that there is a constant 35 nodes I need to search for supposedly puts this into polynomial territory, even though it'll still be a ridiculously high polynomial.

I found an example online using a 3-clique as a question, and it said that enumerating all triples $(u,v,w)$ of nodes in the graph would be a $O(|V|^3)$ complexity... But I don't see how $\displaystyle\frac{|V|!}{3!(|V|-3)!}$ became $|V|^3$...

share|improve this question
1  
Exactly as in Gerry Myerson's answer $\displaystyle\frac{|V|!}{3!(|V|-3)!}=\frac{|V|(|V|-1)(|V|-2)}6$ then you ignore the denominator as you are interested in the power of the leading term. –  Ross Millikan Feb 15 '13 at 5:12
add comment

1 Answer

up vote 1 down vote accepted

The formula you have written reduces to the polynomial $${n(n-1)(n-2)\times\cdots\times(n-34)\over35!}$$

share|improve this answer
    
You'll have to forgive my lack of understanding here.. An example I read online using an arbitrary k value converted the function above to $O(n^k)$, but I have no idea how this happened... –  agent154 Feb 15 '13 at 5:00
    
If you imagine multiplying out the numerator (don't actually do it, just imagine doing it), you will get a polynomial with leading term $n^{35}$ and then terms of smaller degree. Do you understand why such a polynomial is $O(n^{35})$? –  Gerry Myerson Feb 15 '13 at 5:19
    
OK... I see it now. Thanks –  agent154 Feb 15 '13 at 5:21
add comment

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.