0
$\begingroup$

I would like to calculate the complexity of an algorithm using the "inequality strategy".

This algorithm takes two integers as an entry $n, m$. Moreover this algorithm is recursive and if we denote $C_{n,m}$ the number of operations this algorithm does for entry $n, m$ we have the following inequality :

$$C_{n,m} \leq C_{n, (m-1)} + C_{(n-1), (m-1)} + O(1)$$

Moreover the algorithm terminates for the entry : $(0,k)$ and $(k, 0)$ for all $k \in \mathbb{N}$ and $C_{0,k} = O(1)$ and $C_{k, 0} = O(1)$.

So now I need to somehow solve the inequality to get $C_{n,m}$ for all $n, m$. Yet I don't really know how to do this.

The problem is that it seems to me that any function work. For example If I say : $C_{n,m} = O(m)$ then it's tre since by unduction we then have :

$C_{n,m} \leq O(m-1) + O(m-1) + O(1) = O(m-1)$

Moreover If I say that : $C_{n,m} = O(n)$ then it also work since by induction :

$C_{n,m} \leq O(n) + O(n-1) + O(1) $

So what is the problem with I am doing, and how to solve this inequality to get the complexity of $C_{n,m}$ ?

Thank you !

$\endgroup$
1
$\begingroup$

You can’t use $O(m) + O(m) = O(m)$ in an inductive proof, since the hidden constant will keep blowing up. To see this more closely, suppose that you bound $C_{n,m}$ with $A\cdot m$. Then $$ C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq 2A(m-1) + O(1). $$ The right-hand side will generally not be at most $Am$.

Instead, let's try to use Pascal's identity, $\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$. We guess that $C_{n,m} \leq A\binom{m}{n}-B$. Then $$ C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq \\ A\left(\binom{m-1}{n} + \binom{m-1}{n-1}\right) - 2B + O(1) = A \binom{m}{n} - 2B + O(1). $$ For $B$ larger than the hidden constant in $O(1)$, the right-hand side will be at most $A\binom{m}{n} - B$, and so we will be able to prove the induction hypothesis. For given $B$, we can choose large enough $A$ so that $C_{0,k} \leq A \binom{k}{0} - B$ would hold. However, we reach a problem when considering the other base case $C_{k,0} \leq A \binom{0}{k} - B$. Therefore we need to fix our strategy.

At this point, we leave it to the reader to find the right binomial coefficient to add.

$\endgroup$

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.