edited by
1,653 views
4 votes
4 votes

How many term will be computed to determine the value of $10C8$ Using a divide and conquer algorithms ?

  1. 45
  2. 46
  3. 90
  4. 89
edited by

3 Answers

Best answer
5 votes
5 votes

 Explanation: This problem is related to "Binomial coefficient Problem"  but we have to use Divide and Conquer Algorithm.

So we need to find number of function calls required to get the value of 10C8  (i.e. NCR(10, 8) ). We can use following function to get the required answer. 

int NCR(int n,int r) 
{ if(r==0 || r==n) return 0;
else{ return(NCR(n-1, r-1) + NCR(n-1,r)+1);}
}

-------------------------------------------

Shortcut : let X (any value in Pascal's Triangle) is Value of NCR(n,r) and Y be the Number of terms to be computed to determine the value X.

Then Y=2*X-1

i.e. X= NCR(10,8) 

      X=45

     Y=89 (Answer)

selected by
3 votes
3 votes
keep applying pascal identity till a term becomes xCx(=1) or xC0 (=1),  adding 45 1s we will get 10C8..So we  get a binary tree structure if we apply nCr=n-1Cr-1+n-1Cr.once a node becomes 1 we won't expand it further.. So, no of terms =total no of leaves+total no of internal nodes in the tree =45+45-1=89..(no of leave =nCr and no if internal nodes in binary tree =no of leaves-1)

so 89 is the answer
1 votes
1 votes
In worst case 45 terms will be computed

10C8=45

Now if a list is decreasing order

But we want increasing order list then all term will change it place to get perfect ans

Related questions

2 votes
2 votes
2 answers
3
Manasi Srivastava asked Oct 9, 2017
843 views
Do we need to study the Strassens's algorithm in detail like proof or working of that algorithm or we just need to know the time complexity of the algorithm because I can...