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.

New contributor
Tobias Pfandzelter is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    $\begingroup$ In $O(2^n)$ time if you encode $n$ in non-unary, but yes, that makes completely sense. $\endgroup$
    – Pål GD
    Jan 13 at 9:59
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 13 at 10:48

Your Answer

Tobias Pfandzelter is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.