For each pair, the algorithm on the left is significantly less effective than the algorithm on the right.
Try implementing the algorithms and testing them to see just how big a difference an intelligent algorithm can make!
// m choose n version A result = 1 for i = 1 to m result = result * i for i = 1 to n result = result / i for i = 1 to m-n result = result / i return result | // m choose n version B a = max(n, m-n) b = min(n, m-n) result 1 for i = 1 to b result = result * (a + i) / b return result |
Additional note: the intermediate values computed by the first algorithm can be much larger than those computed by the second, meaning it runs into overflow problems for much smaller values of m and n.
// fib(n) version A if (n < 0) return 0 if (n < 2) return 1 return fib(n-1) + fib(n-2) | // fib(n, v=1, p=0) version B // (i.e. an initial call to f(n) is mapped to f(n, 1, 0)) if (n <= 0) return p if (n == 1) return v return fib(n-1,v+p,v) |
// gcd(a, b) version A s = min(a, b) gcd = 1 for c = 2 to s if (a mod c) and (b mod c) are both 0 gcd = c return c | // gcd(a, b) version B L = max(a,b) s = min(a, b) while (s > 0) t = s s = L mod s L = s return L |
// genprimes(n, arr[]) (generate all primes <= n, store in arr) numprimes = 0 for c = 2 to n isprime = true for f = 2 to c if (c mod f) is 0 isprime = false if isprime arr[numprimes] = c numprimes++ return numprimes | // genprimes(n, arr[]) (generate all primes <= n, store in arr) arr[0] = 2 arr[1] = 3 numprimes = 2 c = 5 while c <= n isprime = true i = 0 f = arr[i] while (f*f < c) and isprime if (c mod f) is 0 isprime = false else i++ f = arr[i] if isprime arr[numprimes] = c numprimes++ c += 2 return numprimes |