Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
Try f(n)=g(n)=1. (No (complex-analysis) in here.) –  Did Mar 23 '12 at 9:49
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. marker.to/HR6enQ –  Louis Mar 23 '12 at 10:51

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.