Menu
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.
900
Linear time complexity O(n) means that the algorithms take proportionally longer to complete as the input grows. Examples of linear time algorithms: Get the max/min value in an array.
O(n2) represents a function whose complexity is directly proportional to the square of the input size. Adding more nested iterations through the input will increase the complexity which could then represent O(n3) with 3 total iterations and O(n4) with 4 total iterations.
O(n) is Big O Notation and refers to the complexity of a given algorithm. n refers to the size of the input, in your case it's the number of items in your list. O(n) means that your algorithm will take on the order of n operations to insert an item.
There you go. This is probably the most trivial example of a function that runs in O(n!) time (where n is the argument to the function):
void nFacRuntimeFunc(int n) { for(int i=0; i<n; i++) { nFacRuntimeFunc(n-1); } } One classic example is the traveling salesman problem through brute-force search.
If there are N cities, the brute force method will try each and every permutation of these N cities to find which one is cheapest. Now the number of permutations with N cities is N! making it's complexity factorial (O(N!)).
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
