Asymptotic order of arithmetic functions

21 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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).$$