Prove or disprove the statement: For any positive function $f$, $f(n)$ = $\Omega(f(n/2))$

Question

I have a question in my textbook to prove or disprove the given statement in the title. There is a similar problem asked at $f(n)=\Theta(f(n/2))$. Prove or disprove. , but I'm not 100% sure if the same logic followed from $\Theta$ to $\Omega$. My current theory is that the statement is true since $\Omega$ represents the lower bound of a function $f(n)$, and for simple polynomials, linear equations, and simple logarithmic functions, $f(n/2)$ simply means scaling the function horizontally by a factor of 2. For other more complex examples like $n^n$ or $2^n$, the graph changes in different ways, but I'm not sure if I can predict the changes for all complex examples.

The counter-example given in the other post was $f(n) = 2^n$. For $f(n/2)$, this would translate to $2^{(n/2)}$. I can set both equations equal to each as follows, with $c$ being a constant in the function:

$2^n$ = $c$*$2^{(n/2)}$

We then take the $log_2$ of both sides to get:

$n*log(2)$ = $(n/2)$*$log(2)$+$log(c)$

The $log(2)$'s are clearly equal to one, and are replaced as such to give us:

$n$ = $(n/2)$+$log(c)$

Knowing that $n$ will always be greater than $n/2$, I can safely say that $f(n/2)$ is a good lower bound for $f(n)$ when $f(n)=2^n$. Would there be a way to generalize this statement for all functions? I'm not exactly sure how to go about proving it or what my solution should look like. Any help is greatly appreciated.

P.S. Sorry if my formatting sucks, this is my first time using MathJax and just winged it for the example.

P.S.S The textbook I'm referencing can be downloaded for free at the author's website, https://sites.google.com/site/gopalpandurangan/home/algorithms-course . The specific example I'm working through is Exercise 2.6.ii, from the Chapter "Problem Solving and Algorithms".

Answer 1

Let $f(n)=\exp(2cn)$ and $g(n)=f(n/2)=\exp(cn)=\sqrt{f(n)}$.

Then for $c>0$, $$ \limsup_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|=\limsup_{n\to\infty}\exp(cn)=\infty$$ so that in this case, $f(n)\notin\mathcal O(f(n/2))$.

Likewise, if $c<0$, $$ \limsup_{n\to\infty}\left|\frac{g(n)}{f(n)}\right|=\limsup_{n\to\infty}\exp(-cn)=\infty$$ so that in this case, $g(n)\notin\mathcal O(f(n))$, i.e., $f(n)\notin \Omega(f(n/2))$. Admittedly, $f$ is not a growth function in this case.