0
$\begingroup$

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!

  • 1
    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. http://marker.to/HR6enQ2012-03-23

1 Answers 1

1

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

  • 0
    That is in fact what I meant. I will fix the answer later.2012-03-23