# Possible Mistake in Skiena's Algorithm Design Manual

In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that

$$mn - m^2 + m \in \Omega(mn)$$

where $$m,n \geq 0$$ and $$m \leq n$$. I claim that this is in fact false, with the following proof. Toward a contradiction, suppose otherwise. Then $$mn-m^2 + m \geq cmn$$ where $$m,n > N_{0}$$ for some sufficiently large interger $$N_{0}$$ and some constant $$c > 0$$. Without loss of generality, we may assume that $$c < 1$$ since the RHS above is a lower bound. Then after some rearrangement and canceling terms, we obtain

$$1-c \geq \frac{m-1}{n}.$$

Now recall we can take $$m = n$$, so we obtain

$$1-c \geq \frac{n-1}{n},$$

where the RHS is not greater than $$1$$. However it is easy to see that $$\frac{n-1}{n} \to 1$$ as $$n \to \infty$$. Therefore, given any fixed constant $$0 < c < 1$$, we will be unable to choose a sufficiently large bound $$N_{0}$$ such that when $$m,n > N_{0}$$ the above inequality is satisfied. Thus the original claim is false.

In fact, the claim is apparently still false even under the stronger assumption that $$m - a \leq n$$ for some constant $$a > 0$$. In this case we arrive at the final inequality

$$1-c \geq \frac{n-a+1}{n},$$

where the RHS still converges to $$1$$ as $$n \to \infty$$.

Question: Where did I go wrong above? Did I go wrong above? I would appreciate any feedback addressing any issue with the argument above.

P.S. There exists at least one question on here that also references this equation in the text but the discussion there does not address this particular issue with the claim.

## 1 Answer

You are totally right, though I think there is an easier proof: if $$m = n$$, then $$mn-m^2 +m= m\notin \Omega(m^2)$$.

However, since the analysis is done when searching for a worst case, you could just add a condition $$2m\leqslant n$$ for the analysis to be correct.

But there is indeed a mistake in the analysis by Skiena, that could be clarified.

• Aha! That of course is a much simpler analysis... Many thanks. Commented Feb 29 at 23:31