I understand this should be a relatively easy proof, but I can't seem to understand how to do it.

I know that, by Big O definition:

  • there exists some value $c_1$ where $f(n) \le c_1 \cdot h(n)$ for all $n \ge n_0'$
  • there exists some value $c_2$ where $g(n) \le c_2 \cdot h(n)$ for all $n >= n_0''$

and I have to find some value $c$ and $n_0$ where

$f(n) \cdot g(n) \le c \cdot h(n) \cdot h(n)$ for all $n \ge n_0$

How would I search for those values $c$ and $N_0$? What would the first steps be?

  • 1
    $\begingroup$ Hint: try $C = C_1 C_2$. $\endgroup$ Sep 26 '21 at 0:55
  • $\begingroup$ Second half of hint: consider maximum of $N0'$ and $N0''$. $\endgroup$
    – zkutch
    Sep 26 '21 at 1:08
  • $\begingroup$ Third half of hint: if $a \leq c$ and $b\leq c$, then $ab \leq c^2$. $\endgroup$
    – Pål GD
    Dec 4 '21 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.