Why theta(n^2) if m=floor(n/2) for Naive String-matching
Here is the relevant excerpt from Introduction to Algorithm by CLRS, 3rd edition.


  Procedure NAIVE-STRING-MATCHER takes time $O(n - m +1)m$, and this bound is tight in the worst case. For example, consider the text string $a^n$ (a string of $n$ a’s) and the pattern $a^m$. For each of the $n-m+1$ possible values of the shift $s$, the implicit loop on line 4 to compare corresponding characters must execute $m$ times to validate the shift. The worst-case running time is thus $\Theta((n-m+1)m)$, which is $\Theta(n^2)$ if $m=\lfloor n/2\rfloor$.


Proposition: Let $f(n,m)=\Theta((n-m+1)m)$ be the worst-case running time where $1\le m\le n$. If $m=\lfloor\frac n2\rfloor$, then $f(n,m)=\Theta(n^2)$.

Proof. There are constants $c_1, c_2\gt0$ such that for all $1\le m\le n$, 
$$c_1((n-m+1)m)\le f(n,m)\le c_2((n-m+1)m).$$

Now let $m=\lfloor \frac n2\rfloor$. Since $1\le n+1-2\lfloor\frac n2\rfloor\le2$, for $n\ge2$, 
$$ \begin{align}
\frac{n^2}4&amp;\lt\left(\frac{n+1}2\right)^2-1\\ 
&amp;\le \left(\frac{n+1}2\right)^2-\left(\frac{n+1-2m}2\right)^2=(n-m+1)m\\
&amp;\le\left(\frac{n+1}2\right)^2-\frac14\lt n^2
\end{align}$$
So $$\frac{c_1}4n^2\lt f(n,m)\lt c_2 n^2,
$$
which says $f(n,m)\in \Theta(n^2)$.