# Class P is closed under concatenation

Proving that Class P is closed under concatenation.

But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?

• What are your thoughts? How many times do you think it could be repeated? How many times could the loop iterate? – D.W. May 3 '18 at 0:18
• the number of times equal to the length of w >>> right? @D.W. – Intuition May 3 '18 at 1:06
• Yes. Since n denotes the length of the input, n = length(w). As you noted, step 2 repeats O(length(w)) = O(n) times. – TimD1 May 3 '18 at 2:33
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – Raphael May 3 '18 at 8:28
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael May 3 '18 at 8:28

With $n = |w|$ the length of $w$, step 2 is repeated exactly $n+1$ times.
But they assume implicitly that $n$ is the length of the input (which is canonical in complexity theory), i.e. $|\langle w \rangle|$ with an unspecified encoding $\langle.\rangle$ of strings.
The $O$ (which should be a $\Theta$) comes from that encoding as well. While there are exactly $|w| + 1$ ways to cut $w$ in two parts, we don't know the exact figure in terms of $|\langle w \rangle|$.
They forget to mention their assumption that that encoding is reasonable in a certain way, i.e. $|\langle w \rangle| \in \Theta(|w|)$ for all $w$.
• I suspect that $\langle w \rangle = w$, i.e., there is no encoding involved. Also, the big $O$ is used as an upper bound, so there's no harm in using $O(n)$ rather than $\Theta(n)$. – Yuval Filmus May 3 '18 at 14:08