algorithmtime-complexitybig-oenumeration# Is enumerating combinations of k values from k sets of n values each (one value from each set) polynomial time?

Suppose I am writing a program to enumerate all possible combinations of k values, where each combination contains one value from each of k sets. Each set has n values each.

The input to the program is a single collection of k sets of n values.

I know this would take O(n^k) time (n values to pick from the first set, n values to pick from the second set, and so on). Is this polynomial time, or worse (like O(n^n))?

Not sure how to interpret time complexity.

Solution

The time complexity you described, O(n^k), is not polynomial time in terms of n when k is not a constant value. Polynomial time complexity refers to an algorithm whose running time is a polynomial function of the input size. In this case, the input size is n, so polynomial time complexity would be O(n^c), where c is a constant value.

The running time O(n^k) is called exponential time complexity concerning k. It is not necessarily worse or better than O(n^n), as the relationship between n and k is not specified.

To give you a better understanding, here's a comparison of the complexities:

- Polynomial time complexity: O(n^c) where c is a constant. Examples: O(n), O(n^2), O(n^3), etc.
- Your problem's time complexity: O(n^k) where k is not a constant.
- Exponential time complexity (worse): O(n^n).

Remember that polynomial time complexity is generally considered more tractable or efficient than exponential time complexity, as the running time grows slower concerning the input size.

- Check if Array Is Sorted and Rotated on LeetCode
- Algorithm in hardware to find out if number is divisible by five
- Divisiblity by 5 without using % and / operator
- Fill pattern of an arbitrary size in Intel hex file
- 3D point rotation algorithm
- Hash function for sets of IDs
- Why is my python code so slow (leetcode)?
- Why is heap slower than sort for K Closest Points to Origin?
- How to fix invalid iterator error while using views pipeline and ranges adjacent_find in c++20
- Minimum Time to Perform One Task of Each Category (with Different Release Times)
- Worst case in Max-Heapify - How do you get 2n/3?
- How to check whether a matrix is a framed matrix?
- Identify connected subnetworks, constrained by edge attributes
- Is there a way to generate a random variate from a non-standard distribution without computing CDF?
- Most efficient way to calculate VWAP(VOLUME WEIGHTED AVERAGE PRICE) for trading algorithm
- How to find and replace all occurrences of a substring in a string?
- How to find kth smallest element in a BST when the tree may be modified frequently?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- How does one make a Zip bomb?
- How to calculate the midpoints of each triangle edges of an icosahedron
- Calculate circular shift pairs in a list
- Uniformly randomly generate a vector of k unsigned ints that sums to N
- Bin packing with fixed number of bins of varying capacities and item-to-bin compatibility constraints
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Count Unguarded Cells in the Grid (recursion)
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm