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
    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$2012-10-30
  • 0
    in the second function g(n) is not monotonically increasing function.2012-10-30
  • 1
    @mathemagician $g(n)$ is eventually monotone increasing.2012-10-30
  • 0
    yes you are right, but is this also possible for g(n) and h(n) such that they are monotonically increasing $\forall N$.2012-10-30
  • 0
    @mathemagician Pick a nice $h(n)$ and $g(n)$ below the threshold and then revert to this once you hit the threshold.2012-10-30
  • 0
    sorry i didn't understand what you mean by below the threshold, can you give an example?2012-10-30