Proving that Class P is closed under concatenation.
The answer is given below:
But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?
$\begingroup$
$\endgroup$
-
2$\begingroup$ What are your thoughts? How many times do you think it could be repeated? How many times could the loop iterate? $\endgroup$ – D.W.♦ May 3 '18 at 0:18
-
$\begingroup$ the number of times equal to the length of w >>> right? @D.W. $\endgroup$ – Intuition May 3 '18 at 1:06
-
$\begingroup$ Yes. Since n denotes the length of the input, n = length(w). As you noted, step 2 repeats O(length(w)) = O(n) times. $\endgroup$ – TimD1 May 3 '18 at 2:33
-
$\begingroup$ 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! $\endgroup$ – Raphael♦ May 3 '18 at 8:28
-
$\begingroup$ 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! $\endgroup$ – Raphael♦ May 3 '18 at 8:28
$\begingroup$
$\endgroup$
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.
(Why they insist to introduce that encoding here, I don't know.)
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$.
-
$\begingroup$ 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)$. $\endgroup$ – Yuval Filmus May 3 '18 at 14:08
