[Solved]: How to deal with questions having two or more asymptotic notations

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