Asymptotic notation for $O(1)/\mathsf{poly}(n)$

41 Views Asked by At

Consider $n \in \mathbb{N}$, a constant $s \in O(1)$ and a polynomial value $Q \in \mathsf{poly}(n)$. How can $\frac{s}{Q}$ be written asymptotically? We have $\frac{O(1)}{Q}$, is this value just $o(1)$ for sufficiently large $Q$? If yes, why exactly?

1

There are 1 best solutions below

1
On BEST ANSWER

If $Q$ is a polynomial of degree $d$ and $n$ is large enough, then $cn^d \leqslant Q(n)\leqslant Cn^d$, where $c,C$ are just smaller and larger constants than the lead coefficient respectively.

Thus $$\frac{s}{Cn^d}\leqslant \frac{s}{Q(n)}\leqslant \frac{s}{c n^d},$$ so that $s/Q(n) = O(n^{-d}) = o(1)$, as $n\to\infty$.