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.

I've just had an idea or intuition, but I couldn't be sure if it is correct or not:

Let's say I have a function $f(n)$ such that it can be expressed as $\frac{g(n)}{h(n)}$ where $g(n)$ and $h(n)$ are monotonically strictly increasing functions($\forall n \in N$). $f(n), g(n), h(n)$ are defined on $N \rightarrow R^{\ge 0}$. If $h(n) \in O(g(n))$ such that $h(n)$ is asymptotically bounded by $g(n)$ by given constants $\exists c \in R^{\gt 0}$, $\exists n_0 \in N$ and $\forall n \ge n_0$, in that case can we say that $f(n)$ is a eventually non-decreasing function? If not can you give an counter-example?

Edit: $f(n)$ and $g(n)$ shouldn't be in asymptotically tight-bound. Let's say we know that: $ \lim_{n \rightarrow \infty} \frac{g(n)}{h(n)} \rightarrow \infty$

share|improve this question

1 Answer 1

For a counter example, consider $$h(n) = \exp(n^2)$$ $$g(n) = (1+ \exp(-n)) h(n)$$

EDIT If you want $\lim_{n \to \infty} \dfrac{g(n)}{h(n)} \to \infty$, then consider $$g(n) = (n + 10 \sin(n)) h(n) $$ $f(n)$ oscillates as it goes to infinity.

share|improve this answer
    
well in that case g(n) and h(n) are in asymptotically tight bound, I forgot to mention that they should not be in big-theta. Such that $\lim_{n \rightarrow \infty}\frac{g(n)}{h(n)} \rightarrow \infty$ –  mathemagician Oct 30 '12 at 20:43
    
in the second function g(n) is not monotonically increasing function. –  mathemagician Oct 30 '12 at 21:00
1  
@mathemagician $g(n)$ is eventually monotone increasing. –  user17762 Oct 30 '12 at 21:07
    
yes you are right, but is this also possible for g(n) and h(n) such that they are monotonically increasing $\forall N$. –  mathemagician Oct 30 '12 at 21:20
    
@mathemagician Pick a nice $h(n)$ and $g(n)$ below the threshold and then revert to this once you hit the threshold. –  user17762 Oct 30 '12 at 21:21

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.