Basic Theta-notation question
No. Consider, for instance,
$$T(n,m) = \begin{cases}
m, &amp; \text{$m$ even} \\
\frac{m}{n}, &amp; \text{$m$ odd}
\end{cases}$$
and notice $\frac{m}{f(n)} \le T(n, m) \le m$ holds for $f(n) = n$. Suppose $T(n,m) \in \Theta(m g(n))$ for some $g(n)$, that is, there are $c, c' &gt; 0$ with $cmg(n) \le T(n,m) \le c'mg(n)$ for all but finitely many $m,n$. Since there are infinitely many odd $m$'s we get $g(n) \le \frac{1}{cn}$ for all but finitely many $n$. For even $m$ it then follows
$$m = T(n,m) \le c' m g(n) \le \frac{c'}{c} \frac{m}{n},$$
which can only hold for finitely many $n$.