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?


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.


I take an exception to the problem on which the question is based. The Landau notations should really be interpreted as set relations, i.e., one should really write $f(n) \in O(g)$. Or, as Knuth explains, the right hand side is a "crudification" of the left hand side. As sets, this makes no sense at all.

  • 1
    $\begingroup$ It's common to "lift" functions to apply element-wise to sets. So "$\Omega(\Theta(f))$", which I assume is what you're objecting to, means $\bigcup \{\Omega(f')\mid f'\in \Theta(f)\}$. Maybe it's not helpful to learners to hide so much in the notation but it definitely doesn't "make no sense at all." $\endgroup$ – David Richerby Feb 23 '14 at 13:03

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.