CODEWITHSUNDEEP
calgorithmtime-complexity
user3360041
user3360041

Reputation: 11

different binomial coefficient algorithm's efficiency compare

I've compared two algorithms to calculate binomial coefficient C(n, k) as below: #1 is derived from the formulaic definition of the binomial coefficient to calculate, #2 uses dynamic programming.

#include <stdio.h>
#include <sys/time.h>

#define min(x, y) (x<y?x:y)
#define NMAX 150    

double binomial_formula(int n, int k) {
  double denominator=1, numerator=1, i;
  for (i = 0; i< k; i++)
    numerator *= (n-i), denominator *= (i+1);
  return numerator/denominator;
}

double binomial_dynamic_pro(int n, int k) {
  double c[NMAX][NMAX];
  int i,j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= min(i, k); j++) {
      if (i == j || j == 0)
        c[i][j] = 1;
      else
        c[i][j] = c[i-1][j-1]+c[i-1][j];
    }
  }
  return c[n][k];
}

int main(void) {
  struct timeval s, e;
  int n = 50, k = 30;
  double re = 0;
  printf("now formula calc C(%d, %d)..\n", n, k);
  gettimeofday(&s, NULL);
  re = binomial_formula(n, k);
  gettimeofday(&e, NULL);
  printf("%.0f, use time: %ld'us\n", re,
         1000000*(e.tv_sec-s.tv_sec)+ (e.tv_usec-s.tv_usec));

  printf("now dynamic calc C(%d, %d)..\n", n, k);
  gettimeofday(&s, NULL);
  re = binomial_dynamic_pro(n, k);
  gettimeofday(&e, NULL);
  printf("%.0f, use time: %ld'us\n", re,
         1000000*(e.tv_sec-s.tv_sec)+ (e.tv_usec-s.tv_usec));
  return 0;
}

and I use gcc to compile, and it runs out like this:

now formula calc C(50, 30)..
47129212243960, use time: 2'us
now dynamic calc C(50, 30)..
47129212243960, use time: 102'us

These results are unexpected for me. I thought that dynamic programming should be faster, for it's O(nk), but the formula's method should be O(k^2) and it uses multiplication, which should be also be slower.

So why is the dynamic programming version so much slower?

Upvotes: 0

Views: 435

Answers (2)

mrk
mrk

Reputation: 3191

First algorithm

  • Takes linear time
  • Uses a constant amount of space

Second algorithm

  • Takes quadratic time
  • Uses quadratic amount of space

In terms of time/space, first algorithm is better but the second algorithm has the advantage of computing answer for smaller values as well; it can be used as a pre-processing step.

Imagine that you are given a number of queries of the form n k and you are asked to write n choose k for each of them. Further, imagine that the number of queries is big (say around n*n). Using the first algorithm takes O(nq) = O(n*n*n) while using the second algorithm takes O(n*n).

So it all depends on what you are trying to do.

Upvotes: 0

b4hand
b4hand

Reputation: 9770

binomial_formula as written is definitely not O(k^2). It only has a single loop which is of size k making it O(k). You should also keep in mind that on modern architectures that the cost of memory accesses dwarf the cost of any single instruction by an order of magnitude, and your dynamic programming solution reads and writes many more addresses in memory. The first version can be computed entirely in a few registers.

Note that you can actually improve on your linear version by recognizing that C(n,k) == C(n, n-k):

double binomial_formula(int n, int k) {
  double delominator=1, numerator=1, i;
  if (k > n/2)
      k = n - k;
  for (i = 0; i< k; i++)
    numerator *= (n-i), delominator *= (i+1);
  return numerator / delominator;
}

You should keep in mind that dynamic programming is just a technique and not a silver bullet. It doesn't magically make all algorithms faster.

Upvotes: 2

Related Questions