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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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
@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


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.