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

1 Answer 1

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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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