# Time complexity based on two variables

Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have:

• $T(m,c)\in O(m^2)$ for any constant $c$.
• $T(c',n)\in O(n^2)$ for any constant $c'$.

What can we say about $T(m,n)$?

• I don't have a proof, but my intuition tells me it's $O(m^2 + n^2)$ Apr 1, 2013 at 6:02
• See here and here for thoughts on Landau notation with multiple variables.
– Raphael
Apr 2, 2013 at 8:03

With this exact phrasing, and without additional assumptions on the structure of $T$, you can't really say anything about it's asymptotic behavior in general.
First, observe that the function $m^2n^2$ satisfies the constraints, so you can at least $\Omega(m^2n^2)$. However, you can get much more than that.
Let $f(k)$ be some function. Think of $f$ as a very quickly-growing function (e.g. $f(k)=2^k$).
Now, think of $\mathbb{N}^2$ as a two dimensional plane, with the $m$ and $n$ axes. We require that along every vertical and every horizontal line, the function is asymptotically quadratic. This means that we can do whatever we want with finitely many elements of every row/column.
Thus, for example, you can set $T(k,k)=f(k)$ for every $k$, and set $T(m,n)=m^2n^2$ for all entries where $m\neq n$.
The diagonal of this function is huge. That is, $T(k,k)=\Omega(f(k))$. However, the function still satisfies the constraints. Also, note that you can make this function monotonic by adding $f(k)$ to all elements in the relevant row/column. That is, take $$T(m,n)=f(\min\{m,n\})+m^2n^2$$ This still has the same property, only here we change finitely many elements, instead of a single element.