Does a set definition have computational complexity?

Question

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.

Answer 1

Usually, mathematical definitions are not computational. Informally, mathematics describes the "what", not "how" you compute it.

However, for some problems there is an obvious algorithm deciding them. I would not see an issue with a sentence like this:

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

Yet, the set definition still does not carry any computational behavior. It's just that it is decidable, and you consider finding a decision procedure with the stated complexity trivial enough for your target audience. The decidability does not depend on how you define it.