# complexity classes defined as limits or “globally”?

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$$?

• 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$. – ttnick Nov 2 '18 at 11:12
• @PHPNick "Considering decision problems, you only look at finite n." -- citation needed. – Raphael Nov 2 '18 at 13:56
• @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. – ttnick Nov 2 '18 at 14:39
• 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. – DreamConspiracy Nov 2 '18 at 14:48
• There is a field called concrete complexity which studies the complexity of (cryptographic) algorithms for finite values of $n$. – Yuval Filmus Nov 2 '18 at 16:09