# Why theta(n^2) if m=floor(n/2) for Naive String-matching

I’m reading CLRS(Introduction to Algorithm, 3rd edition). In the chapter 32.1 about the naive string-matching algorithm, the book says the worst case running time is $$\Theta(n^2)$$ if $$m = \lfloor \frac n2\rfloor$$. I get that when $$m$$ equals $$\frac n2$$, but I don’t see it when $$m$$ is less than $$\frac n2$$. Any hint or suggestion is very appreciated! m is the length of the pattern string, n is the length of the text to be searched for the pattern. The book uses (n-m+1)m to calculate the running time.

• What do $m$ and $n$ mean here? – Draconis Jan 19 at 22:52
• I don't get your question. What's your confusion? What's your understanding if $n$ is odd? – Raphael Jan 19 at 22:59
• My understanding is that the running time has to be some quadratic function so it can be theta(n^2). So if m is not n/2, I don’t understand how (n-m+1)m can become a quadratic expression whose highest term is n^2. – user917099 Jan 19 at 23:06
• Do you find $(n * ( n / 100 000 000))$ to be $\mathcal \Theta(n^2)$ or not? – Evil Jan 20 at 1:27
• I see but if this is the thought behind, what about n * (2/3n) for the situation that m is not floor but the ceiling of n/2? – user917099 Jan 20 at 1:29

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&\lt\left(\frac{n+1}2\right)^2-1\\ &\le \left(\frac{n+1}2\right)^2-\left(\frac{n+1-2m}2\right)^2=(n-m+1)m\\ &\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)$$.