What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.
What is an example (in code) of a O(n!) function? It should take appropriate number of operations to run in reference to n; that is, I'm asking about time complexity.
This is a simple example of a function with complexity O(n!) given an array of int in parameter and an integer k. it returns true if there are two items from the array x+y = k , For example : if tab was [1, 2, 3, 4] and k=6 the returned value would be true because 2+4=6
public boolean addToUpK(int[] tab, int k) {
boolean response = false;
for(int i=0; i<tab.length; i++) {
for(int j=i+1; j<tab.length; j++) {
if(tab[i]+tab[j]==k) {
return true;
}
}
}
return response;
}
As a bonus this is a unit test with jUnit, it works fine
@Test
public void testAddToUpK() {
DailyCodingProblem daProblem = new DailyCodingProblemImpl();
int tab[] = {10, 15, 3, 7};
int k = 17;
boolean result = true; //expected result because 10+7=17
assertTrue("expected value is true", daProblem.addToUpK(tab, k) == result);
k = 50;
result = false; //expected value because there's any two numbers from the list add up to 50
assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
}
In JavaScript:
// O(n!) Time Complexity
const {performance} = require('perf_hooks');
const t0 = performance.now()
function nFactorialRuntime(input){
let num = input;
if (input === 0) return 1;
for(let i=0; i< input; i++){
num = input * nFactorialRuntime(input-1);
}
return num;
}
const t1 = performance.now()
console.log("The function took: " + (t1 - t0) + " milliseconds.")
nFactorialRuntime(5);
for node 8.5+, you need to first include performance from the perf_hooks module. Thank you.