# Asymptotic functions

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?

Thanks!

-
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

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

-
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