7
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Aha! That of course is a much simpler analysis... Many thanks. $\endgroup$
    – Joshua
    Feb 29 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.