I have the expression:
$$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$
which runs until k = n or m.
What is the big theta of this function in terms of n,m?
A naive approach is to assume that m does not vary at all since:
$f_k(n,m) < (n - k)m + f_{k+1}(n,m) $
Which gives the expression:
$$nm + (n-1)m + (n-2)m. .. = m\frac{n^2 + n}{2} = O(mn^2)$$
But I want a tighter bound given that we are working with:
$$nm + (n-1)(m-1) + (n-2)(m-2) ... $$
Assume $n>m$. Then the expression you are currently working with has m terms. Expanding each expression of the form $(n-a)(m-a)=nm-an-am+a^2$ and regrouping like terms and taking their sum, we get:
$nm^2-n(m(m+1)/2)-m(m(m+1)/2)+m(m+1)(2m+1)/6$
After simplifying the expression, you should get the tight bound.