Proving that Class P is closed under concatenation.

The answer is given below:

enter image description here

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

  • 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

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

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.