# Can we do it in O(n) time?

Let us suppose we maintain a single 1D array to compute the factorials up to n. We can use computed factorial value and apply the formula P(n, k) = n! / (n-k)!. Below is a program illustrating the same concept.

The Permutation Coefficient represented by P(n, k) is used to represent the number of ways to obtain an ordered subset having k elements from a set of n elements.

Permutation refers to the process of arranging all the members of a given set to form a sequence. The number of permutations on a set of n elements is given by n! , where “!” represents factorial.

`// A O(n) solution that uses`

`// table fact[] to calculate`

`// the Permutation Coefficient`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`// Returns value of Permutation`

`// Coefficient P(n, k)`

`int` `permutationCoeff(` `int` `n, ` `int` `k)`

`{`

`` `int` `fact[n + 1];`

`` `// Base case`

`` `fact = 1;`

`` `// Calculate value`

`` `// factorials up to n`

`` `for` `(` `int` `i = 1; i <= n; i++)`

`` `fact[i] = i * fact[i - 1];`

`` `// P(n,k) = n! / (n - k)!`

`` `return` `fact[n] / fact[n - k];`

`}`

`// Driver Code`

`int` `main()`

`{`

`` `int` `n = 10, k = 2;`

``

`` `cout << ` `"Value of P("` `<< n << ` `", "`

`` `<< k << ` `") is "`

`` `<< permutationCoeff(n, k);`

`` `return` `0;`

`}`

Output :

Value of P(10, 2) is 90

A O(n) time and O(1) Extra Space Solution

`// A O(n) time and O(1) extra`

`// space solution to calculate`

`// the Permutation Coefficient`

`#include <iostream>`

`using` `namespace` `std;`

`int` `PermutationCoeff(` `int` `n, ` `int` `k)`

`{`

`` `int` `P = 1;`

`` `// Compute n*(n-1)*(n-2)....(n-k+1)`

`` `for` `(` `int` `i = 0; i < k; i++)`

`` `P *= (n-i) ;`

`` `return` `P;`

`}`

`// Driver Code`

`int` `main()`

`{`

`` `int` `n = 10, k = 2;`

`` `cout << ` `"Value of P("` `<< n << ` `", "` `<< k`

`` `<< ` `") is "` `<< PermutationCoeff(n, k);`

`` `return` `0;`

`}`

Output :

Value of P(10, 2) is 90