0
$\begingroup$

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$

1 Answers 1

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.

  • 0
    sorry i didn't understand what you mean by below the threshold, can you give an example?2012-10-30