1
$\begingroup$

As far as I understand correctly, to say that a decision problem $X$ is in P means that there exists a polynomial $c\cdot n^p$ such that as $n$ goes to $\infty$, the steps required to solve $X$ is bounded by $c\cdot n^p$.

But strictly speaking, this doesn't restrict the complexity for finite $n$ in any way. Strictly speaking if $X$ is in P, it could be that for all $n$ between $0$ and Ackermann function $A(300,300)$, the complexity of $X$ grows according to $e^n$, and then only from $A(300,300)$ onwards it starts being bounded by $c\cdot n^p$.

Am I right that if a problem is in the complexity class P this strictly speaking doesn't say anything about its complexity for finite $n$? Is there a way to talk about complexity for finite $n$?

$\endgroup$
  • $\begingroup$ Considering decision problems, you only look at finite $n$. Moreover, if you have a polynomial $cn^p$ that is an upper bound on the running time for $n \geq A(300,300)$ then you can also find a polynomial for $n < A(300, 300)$. In fact, for any $n_0 \in \mathbb{N}$ you find some polynomial that is larger than $e^n$ for all $n \leq n_0$. $\endgroup$ – ttnick Nov 2 '18 at 11:12
  • $\begingroup$ @PHPNick "Considering decision problems, you only look at finite n." -- citation needed. $\endgroup$ – Raphael Nov 2 '18 at 13:56
  • $\begingroup$ @Raphael What I meant was that we do not consider decision problems where inputs can be infinite, when talking about complexity. This would not make sense at all. $\endgroup$ – ttnick Nov 2 '18 at 14:39
  • 1
    $\begingroup$ One important thing to note is that if you have a bound on the input size, you can always write a constant time algorithm in the form of a lookup table. This isn't a complete answer, but it does get at some of the reasons that we only talk about formal complexity asymptotically. $\endgroup$ – DreamConspiracy Nov 2 '18 at 14:48
  • 1
    $\begingroup$ There is a field called concrete complexity which studies the complexity of (cryptographic) algorithms for finite values of $n$. $\endgroup$ – Yuval Filmus Nov 2 '18 at 16:09
1
$\begingroup$

Complexity classes are (usually) expressed using Landau notation, which makes precise what you state. See also our reference questions.

Yes, by definition (usual) complexity classes don't say anything about the real world per se. That is by design; complexity is a model for classifying the inherent hardness problems, not a tool to design or analyse algorithms. See also here for some related thoughts.

Is there a way to talk about complexity for finite n?

"Complexity" and "finite" are mutually exclusive. Of course you can study, say, the (relative) performance of algorithms on real(istic) data. The machinery of complexity theory and, sadly, "Big-Oh"-driven algorithm analysis will be mostly useless then.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.