Example of O(n!)?

Viewed 89008

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.

17 Answers

Add to up k function

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.

Related