4
$\begingroup$

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

$\endgroup$

migrated from cstheory.stackexchange.com Apr 1 '13 at 5:35

This question came from our site for theoretical computer scientists and researchers in related fields.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.