$f(n) = \mathcal{O}(g(n))$ then $\prod_{i=1}^n f(i) = \mathcal{O} \left( \prod_{j=1}^n g(j) \right)$?

42 Views Asked by At

I have $f$ and $g$ two functions that are $f,g : \mathbb{N} \to \mathbb{R}_+$ is the following true or false?

$f(n) = \mathcal{O}(g(n))$ then $\prod_{i=1}^n f(i) = \mathcal{O} \left( \prod_{j=1}^n g(j) \right)$

1

There are 1 best solutions below

0
On BEST ANSWER

Take $f=2g$. Then clearly $f(n) = O(g(n))$ for $n\to\infty$, but $$ \prod_{i=1}^n f(i) = 2^n \prod_{i=1}^n g(i) $$ so that $$ \frac{\prod_{i=1}^n f(i)}{\prod_{i=1}^n g(i)} = 2^n \xrightarrow[n\to\infty]{} \infty\,. $$ This shows that $\prod_{i=1}^n g(i) = o\left(\prod_{i=1}^n f(i)\right)$, and therefore $$ \prod_{i=1}^n f(i) \notin O\left(\prod_{i=1}^n g(i)\right)\,. $$