If $f,g:\mathbb{N}\rightarrow\mathbb{R}$ are two functions such that $f(n)=O(g(n))$, then what can we say about the order of $\prod_{i=1}^nf(i)$ in terms of $g(\cdot)$?
Any suggestion is welcome.
If $f,g:\mathbb{N}\rightarrow\mathbb{R}$ are two functions such that $f(n)=O(g(n))$, then what can we say about the order of $\prod_{i=1}^nf(i)$ in terms of $g(\cdot)$?
Any suggestion is welcome.
By definition
$$f(n)=O(g(n))\implies \exists I:\forall i\ge I:f(i)\le c\,g(i)$$ Then $$\prod_{i=I}^n f(i)\le c^{n-I}\prod_{i=I}^n g(i)$$
and ignoring the constant factors,
$$\prod_{i=1}^n f(i)=O\left(c^n\prod_{i=1}^n g(i)\right).$$
Under certain hypothesis,
$$\prod_{i=1}^n g(i)=O\left(e^{\int_1^n\log(g(t))\,dt}\right).$$