1
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ My textbook mentions that $c>0$, meaning your first example is true, but I think the second example would be irrelevant (unless I misunderstood what my textbook is trying to say). Also, the constant $c$ I used was a reference to the definition of $\Omega$, where $f(n) >= cg(n)$. $\endgroup$
    – Mayman
    Jul 7, 2021 at 8:30
  • $\begingroup$ Actually, thinking about your comment more carefully, I see that the statement is false. I don't think the question particularly cared about growing or shrinking functions, simply that the function be positive (meaning greater than 0 for n greater than 0). Using your example but simplifying it, if $f(n) = 2^{-n}$, then $f(n/2) = 2^{-n/2}$. Taking the log of both functions and simplifying, I get to the conclusion that $log(f(n)) = -n$, and $log(g(n) = -n/2$. It is easy to see that $-n < -n/2$ for large enough n, and therefore the statement from my textbook has been dis-proven. Thank you! $\endgroup$
    – Mayman
    Jul 7, 2021 at 8:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.