Take the 2-minute tour ×

Someone can help me to identify a function $f$ and a functon $g$ which statisfy the conditions specified below:

  • $f(n) = \operatorname{O}(g²(n))$

  • $f(n) = \Omega(f(n)g(n))$

  • $f(n) = \Theta(g(n)) + \Omega(g²(n)))$

How is the approach to solve such a problem?


share|improve this question
Try f(n)=g(n)=1. (No (complex-analysis) in here.) –  Did Mar 23 '12 at 9:49
Something about how asymptotic notation is being taught is off, since almost the exact same questions come up again and again. Anyway, Peter Braß has written a book on the topic, which you might want to look at. marker.to/HR6enQ –  Louis Mar 23 '12 at 10:51
add comment

1 Answer

The first thing to try is to use constant functions (see Didier's comment). You will find that if you take $f$ and $g$ as arbitrary constant functions (e.g., $f \equiv 1, g \equiv 2$), all conditions hold.

Assume now that $f(n)$ is positive (i.e., $f(n) > 0$ for all $n \in \mathbb N$). Then by $f(n) = \Omega(f(n)g(n))$, you find $g(n) = O(1)$, and by further calculation, $f(n) = O(g^2(n))$ implies $f(n) = O(1)$. In fact, if you also assume that $g(n)$ is positive, all conditions hold iff $f(n), g(n) = O(1)$.

In other words, any two functions that are bounded and positive will do.

If one of the functions may have zeroes, more solutions may become possible.

Edit: As stated in the comments, "bounded and positive" should be read as "take values in some interval $[l,u]$ with $l,u$ positive".

share|improve this answer
any two functions that are bounded and positive will do... Nope, except if by bounded and positive one means uniformly in [c,C] for some positive finite c and C. –  Did Mar 23 '12 at 11:06
That is in fact what I meant. I will fix the answer later. –  Johannes Kloos Mar 23 '12 at 12:11
add comment

Your Answer


