Trying to prove:
If $f(n)$ and $g(n)$ are both $O(h(n))$,
then
$f(n)*g(n)$ is
$O(h^2(n))$.
Understanding so far : The product of upper bounds of functions gives an upper bound
for the product of the functions:
proof:
If $g_1(n) \le c_1\ f_1(n)$
for $n > n_1$ and
$g_2(n) \le c_2f_2(n)$
for $n > n_2$,
then
$g_1(n)g_2(n)
\le c_1c_2f_1(n)f_2(n)$
for $n > \max(n_1,n_2)$
.
Any ideas??
.
Best Answer
The definition of big O notation tells us that $\lim_{n\to\infty} \left|\frac{f(n)}{h(n)}\right|$ is a constant and similarly for $g(n)$. Thus $$\lim_{n\to\infty} \left|\frac{f(n)}{h(n)}\right|\left|\frac{g(n)}{h(n)}\right|=\lim_{n\to\infty} \left|\frac{f(n)g(n)}{h(n)^2}\right|$$ is a constant, which means $O(fg)=O(h^2)$.