2

Exercise: Prove that the computational complexity of the binomial coefficient \begin{equation*} \binom{m}{n} \end{equation*} is O($m^{2}$$\log^{2}n$). using the fact that the computanional complexity of the product of s+1 integers is O($s^{2}\log^{2}M$) where M is the max of them and that T($m!$)=O($m^{2}\log^{2}m$). I tried with this \begin{equation*} \binom{m}{n} = \frac{m!}{n!(m-n)!}=\frac{m(m-1)\dots(m-n+1)}{n!} \end{equation*}

So for the numerator we have a computaniol complexity O($(n+2)^{2}\log^{2}m$) because we have n+2 product of integers smaller than m and for the denominator we have a computational complexity O($n^{2}\log^{2}n^{2}$). Now i know that the coast of the division between two number is T($m=qn+r$)=O($\log q\log n$)=O($\log^{2}n$) since $q<n$. From now on i don't know how to proceed.

Bar
  • 91
  • 1
    When you get a satisfactory answer for a question of yours, you can accept it. Please, take a tour to see how to accept answers and what are the basic functionalities on this site. – frabala Apr 02 '14 at 11:36

1 Answers1

1

On the numerator you multiply $n$ integers, so the complexity is $O((n-1)^2\log^2 m)=O(n^2\log^2m)$.

Also, about the complexity of computing the denominator, you have that $$O(n^2\log^2n^2)=O(4n^2\log^2n)=O(n^2\log^2n)$$

And for the division, you have $O(\log^2 n!)=O\left(\left(\sum_{i=1}^n\log i\right)^2\right)=O\left(\left(\sum_{i=1}^n\log n\right)^2\right)=\left(\left(n\log n\right)^2\right)=O(n^2\log^2 n)$

The total complexity is the sum of the complexity of computing the numerator, then the denominator and finally do the division. So, you have \begin{align} &O((n-1)^2\log^2 m)+O(n^2\log^2n^2)+O(\log^2 n!)\\ =&O(n^2\log^2m)+O(n^2\log^2n)+O(n^2 \log^2 n)\\ =&O(n^2\log^2 m)&\text{ since } n<m \end{align}

frabala
  • 3,732