# Does a set definition have computational complexity?

I'm wondering if a mathematical set definition has a computational complexity.

For example, assume I have some kind of problem where the solution is given by the positive integers smaller than a given integer $$n$$:

$$M = \{ x | x < n, x \in \mathbb{N} \}$$

Could I say this problem can be solved in $$\mathcal{O}(n)$$ because I could realistically construct an algorithm that yields this result in linear time?

I actually have such an approach in a paper where it makes more sense to define a set than give an (trivial) algorithm that returns this set.

• In $O(2^n)$ time if you encode $n$ in non-unary, but yes, that makes completely sense. Jan 13 at 9:59
• When you say $\mathcal{O}(n)$ you probably do not mean the $n$ from the defintion of the set but the size of the input. Since your set is finite, it can be decided by a mere table lookup. Depending on your model of computation, the complexity for this can even be less than linear. At any rate, "problems" in complexity theory are sets, so it makes perfect sense to attribute a complexity to them. Not the "set definition has a computational complexity" but the set. Jan 13 at 10:48

The problem $$\{x \in \mathbb N\,|\, x < c\}$$ can be decided in $$O(n)$$ for all constants $$c$$.