0

I have a function $f(n)$ defined over $n \in \mathbb{N}$ which I would like to bound asymptotically. I have proven that $f(a) \leq g(a)$ for some subset of naturals $a \in A \subset \mathbb{N}$ and I know $g(n) \sim h(n)$. The function $g(n)$ is rather ugly, but $h(n)$ is simple, so I would prefer to relate the growth of $f$ to $h$ instead of $g$. If I could show $f$ was monotone, (I think) that would be enough to claim $f(n) \sim \textrm{O}(h(n))$, but for the time being I am unable to show that.

My question is: is there a meaningful way to denote this relationship? I initially tried saying $f(n) \leq h(n)$ for infinitely many $n \in \mathbb{N}$, but we can't even say that because we only know: $$\lim_{n \to \infty} \frac{g(n)}{h(n)}=1$$ Maybe I'm looking for something like $f(n) \lesssim h(n)$, but I do not know exactly what this symbol means. Does anyone know how I should describe this relation?

Edit: I've done some thinking about the examples provided in the comments and I think I thought of a reasonable way to describe this relation. The most "meaningful" description I can use under the given information is that $f(n) \neq \omega(h(n))$. This is a slightly weaker claim than $f(n) = \textrm{O}(h(n))$, which I do not have enough information to claim as is, but I think this is still a nice characterization using asymptotic notation.

Ryan Farrell
  • 1
  • 1
  • If you can't give an inequality true for all $n$, and if you can't verify monotonicity of $f$, then things can be arbitrarily bad and I see no reasonable answer to your question. For instance, maybe $h(n)=0$ for all $n$, and for odd $n$ we have $f(n)=0$, and for all even $n$ we have $f(n) = n^{n^{n^{n^{\ldots^n}}}}$ (with $e^n$ exponents in all). – Lee Mosher Feb 12 '24 at 18:31
  • This also depends on what "some" subset $A$ is. You better show that $\mathbb N\setminus A$ is finite ... – Hagen von Eitzen Feb 12 '24 at 19:22
  • Also note that with $f(n)=-n^2$, $g(n)=h(n)=n$, we do have $f(n)\le g(n)$ for all $n\in\mathbb N$, and we do have $g(n)\sim h(n)$, but certainly not $f(n)=O(h(n))$. – Hagen von Eitzen Feb 12 '24 at 19:25
  • Yes, you all make good points - there is no reason the function should remain unbounded between the known-bounded values in $A$. And no, $\mathbb{N} \setminus A$ is not finite, so I can't work with that. But it is still notable that $f(n)$ still dips down to the "smaller" $h(n)$ values infinitely often, which is the fact I want to capture. My question is "what is good notation for such a fact"?

    Also, all of the functions in question are positive-valued, so my concern is more towards the issues with the even/odd counterexample as opposed to the $-n^2$ counterexample.

     – Ryan Farrell Feb 13 '24 at 03:49

0 Answers0