patternMinor
Time complexity based on two variables
Viewed 0 times
timetwobasedvariablescomplexity
Problem
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:
What can we say about $T(m,n)$?
- $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)$?
Solution
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.
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.
Context
StackExchange Computer Science Q#10955, answer score: 4
Revisions (0)
No revisions yet.