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.

  • $\begingroup$ What do $m$ and $n$ mean here? $\endgroup$ – Draconis Jan 19 '19 at 22:52
  • $\begingroup$ I don't get your question. What's your confusion? What's your understanding if $n$ is odd? $\endgroup$ – Raphael Jan 19 '19 at 22:59
  • $\begingroup$ 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. $\endgroup$ – user917099 Jan 19 '19 at 23:06
  • $\begingroup$ Do you find $(n * ( n / 100 000 000))$ to be $\mathcal \Theta(n^2)$ or not? $\endgroup$ – Evil Jan 20 '19 at 1:27
  • $\begingroup$ 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? $\endgroup$ – user917099 Jan 20 '19 at 1:29

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&\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)$.


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.