Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
