[Solved]: Time complexity based on two variables

Problem Detail: 

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)$?

Asked By : Naji

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10955