Finding a complexity by solving inequality

Question

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 !

Answer 1

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.