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?
Asked
Active
Viewed 38 times
0
-
Is $n\to\infty$? Otherwise, it depends on the roots of $Q$. – Luke Collins Feb 14 '23 at 09:38
-
If $Q$ is a (non-zero) constant polynomial, $s/Q$ is only $O(1)$ or simply: a constant, like $s.$ – Anne Bauval Feb 14 '23 at 09:40
-
$s$ is constant implies $s\in O(1)$. – zkutch Feb 14 '23 at 09:47
1 Answers
2
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$.
Luke Collins
- 8,748