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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityProving 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?
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$.