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:

    1. Polynomial time complexity: O(n^c) where c is a constant. Examples: O(n), O(n^2), O(n^3), etc.
    2. Your problem's time complexity: O(n^k) where k is not a constant.
    3. 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.