# Finding a complexity by solving inequality

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 !

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.