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?
2026-04-24 11:20:10.1777029610
Asymptotic notation for $O(1)/\mathsf{poly}(n)$
41 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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$.