# Basic Theta-notation question

Let $$T$$ be a function.

Is it true that if $$\exists f\forall n,m> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$$

Then $$\exists g.T(n,m)=\Theta(m\cdot g(n))$$?

In words: is such a case, is there a function $$g$$ dependent only on $$n$$ that satisfies the above?

It looks to me true, but I am really stuck and don't know how to prove it rigorously.

No. Consider, for instance, $$T(n,m) = \begin{cases} m, & \text{m even} \\ \frac{m}{n}, & \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' > 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$$.
• Thanks! What happens if I assume that $f$ is non-decreasing? – Dudi Frid Aug 23 '19 at 8:19
• @DudiFrid I suppose you can modify $T$ so it still "jumps" between $\frac{m}{n}$ and $m$ but stretch them out enough so it's non-decreasing. The definition will be very ugly, though. – dkaeae Aug 23 '19 at 8:32