HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Basic Theta-notation question

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thetaquestionnotationbasic

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#112996, answer score: 5

Revisions (0)

No revisions yet.