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.
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:
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.