Find number of combinations, nCr in O(1)

Question

Is there a way to find the number of combinations (not the actual combinations), in O(1)? I read an answer here - time and space complexity of finding combination (nCr). The answer says that it takes O(n!) to find the actual combinations but only takes O(1) to find the number of such combinations. I couldn't understand how it can be done. Please explain me how to do that in O(1). Here, O(1) is time complexity.

[edit]:The main problem I'm having is how to implement n! in O(1).

Answer 1

Please check the below C program. It takes n and r as input and calculates ⁿC_r value:

int main(){
    int n, r;
    scanf("%d", &n);
    scanf("%d", &r);

    /*
    *  nCr = n! / !(n-r) / !(r)
    *      = n * n-1 * n-2 * .... * 1 / (n-r * n-r-1 * .. * 1) / 
    *           (r * r-1 * ... * 1)
    *      = n * n-1 * n-2 * n-r+1 / (r * r-1 * ... * 1)
    *      
    */

    int result = 1;
    int i;

    for (i=0; i<r; i++){
        result *= (n-i);    // n * n-1 * n-2 * .... * n-(r-1)
        result /= (i+1);    // r * r-1 * ... * 1
    }

    /*  The loop is going to run only r times for any n
     *  Time to calculate nCr : O(r)
     *  Space complexity: O(1)
    */

    printf("Result of C(%d, %d) = %d", n, r, result);

    return 0;
}

To calculate it, the loop runs only for 'r' times.

Hence, time complexity to calculate nCr value is O(r) But space complexity is O(1)

I guess you must have been confused with these two complexity orders. Hope, it helps you.

Answer 2

If you are trying to calculate n! in constant time, why not use Stirling's Approximation?

n! \approx sqrt(2 * pi * n) * (n / e)^n

or in C:

pow( n, n ) * exp( -n ) * sqrt( 2.0 * PI * n );

I think this will get you the closest to constant time, the actual run time of each of those operations is architecture dependent.

Sources:

https://en.wikipedia.org/wiki/Stirling%27s_approximation

https://github.com/ankurp/C-Algorithms/blob/master/factorial/fact.c

Answer 3

The run-time complexity of nCr can only be in O(1) if the computing platform you use computes n! in O(1). On a standard computer, this is not the case.

But we can use the fact that exp(n) and log(n) is usually an O(1) operation for IEEE doubles and implement an approximation of log(n!) - based on Stirling's approximation - in O(1):

logf(n) = log(n!) = (n – 0.5) * log(n) – n + 0.5 * log(2 * PI) + 1/(12 * n)

If we combine this with a lookup-table for log(n!) for n ≤ 255 we will still have at least 14 significant figures and we can compute a very good approximation of nCr as follows:

binomial(n, r) = exp(logf(n) - logf(n - r) - logf(r))

Answer 4

Ajeet's answer should be accepted, but I think it can be improved to Min(O(r),O(n-r)) which is still O(r) if reduced.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System. in );
        int n = sc.nextInt();
        int r = sc.nextInt();
        // choose smaller one
        if (n - r < r) { 
            r = n - r;
            System.out.printf("Change %d to %d\n", n - r, r);
        }
        /*
         * nCr  = n! / ((n-r)! * (r)! )
         *      = (n * n-1 * n-2 * .... * 1) / ( (n-r * n-r-1 * .. * 1) * (r * r-1 * ... * 1) )
         *      = (n * n-1 * n-2 * n-r+1) / (r * r-1 * ... * 1)
         */

        int result = 1;

        for (int i = 0; i < r; i++) {
            result *= (n - i); // n * n-1 * n-2 * .... * n-(r-1)
            result /= (i + 1); // r * r-1 * ... * 1
        }

        /*
         * The loop is going to run only r times or (n-r) times for any n Time to calculate nCr : Min ( O(r) , O(n-r) )
         * Space complexity: O(1)
         */
        System.out.printf("Result of C(%d, %d) = %d", n, r, result);
    }
}

Answer 5

In some of the use cases, it might be best to precompute all the answers in O(n^2) by generating pascal's triangle, so that the queries are O(1).

Other times you just have to calculate n! one by one so the complexity would be O(n).