patternMinor
Possible Mistake in Skiena's Algorithm Design Manual
Viewed 0 times
designmanualmistakealgorithmpossibleskiena
Problem
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 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.
$$
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 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.
Solution
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.
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.
Context
StackExchange Computer Science Q#165700, answer score: 6
Revisions (0)
No revisions yet.