Problem Detail: The following was asked as part of a homework assignment and I am not asking for the solution to these but rather tips or resources on how to solve this and similar questions, Let $f(n)$ and $g(n)$ be two functions from $mathbb{N}^+$ to $mathbb{R}^+$. Prove or disprove the following assertions. To disprove, you only need to give a counter example for functions $f(n)$ and/or $g(n)$ which make the assertion false. Consider the following. $$Omega(Theta(f(n))) = Omega(f(n))$$ According to me the answer is false in this case, my reasoning is that whenever we say $f(n)=Theta(g(n))$ we are saying that $f(n)$ will always lie between the limits of $g(n)$. Here, let’s say $x(n) = Theta(f(n))$ so it will always lie between the function $f(n)$ then we take $Omega(x(n))$ which would mean that $y(n)$ will always be greater than $x(n)$, and on the right hand side we compare it to some $a(n)$ which is equal $Omega(f(n))$ meaning that $a(n)$ will always be greater than $f(n)$. Hence we cannot say correctly if the relation will hold, it may or may not be true. Is this the correct way of looking at the problem, is there a better way to solve these questions?
Asked By : g90
Answered By : Artem Kaznatcheev
No, this is not the right way to think about this question. To get you on the right track notice that $f(n) in Theta(f(n))$ no matter what. This should give you the right intuition. However, you can’t prove equality with just one function taken from $Theta(f(n))$ you have to consider an arbitrary function. If you work through carefully (I won’t give you the step-by-step since active learning is important), you will see that $Omega(Theta(f(n))) = Omega(f(n))$. To test your understanding after you figure this out, make sure that you can also show that $Omega(O(f(n))) neq Omega(f(n))$. The intuition you should keep in mind (that you have to make rigorous by carefully understanding this table) is that $Omega$ is kind of like $geq$, $O$ is kind of like $leq$ (for lower case of both, make them strict inequalities), and $Theta$ is kind of like $=$. But this is only heuristic intuition. Make it precise on your own, and see if you can find any weird functions that might serve as counter-examples.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21724
