0
$\begingroup$

Prove $$f_1(n) * f_2(n) = O (g_1(n)*g_2(n))$$

Given: $f_1(n) = O(g_1(n)) , f_2(n) = O(g_2(n))$

So I started by saying:

$\exists n_0,c_1 , \forall n \gt n_0 : f_1(n) \le c_1\cdot g1(n)$

$\exists n_1,c_2 , \forall n \gt n_1 :f_2(n) \le c_2\cdot g2(n)$

Then,

$\forall n \gt max\{n_0,n_1\}: f_1(n)\cdot f_2(n) \le c_1\cdot g_1(n) \cdot c_2\cdot g_2(n) \le c_1c_2 \cdot max\{g_1(n),g_2(n)\}$

From $max\{n_0,n_1\}$ I take $n_0$ for example, and $c = c_1c_2$

Does this proof works?

Taken from Introduction to Algorithms 2nd book.

Answer: (After fix)

$\forall n \gt max\{n_0,n_1\}: f_1(n)\cdot f_2(n) \le c_1\cdot g_1(n) \cdot c_2\cdot g_2(n) \le c_1c_2 \cdot max\{g_1(n) \cdot g_2(n)\}$

$\endgroup$
  • 1
    $\begingroup$ The maximu of $g_1$ and $g_2$ should be their product but apart from that, yes, this is the way to go. $\endgroup$ – Did Aug 14 '16 at 11:33
  • $\begingroup$ @Did I see, thanks Did! $\endgroup$ – Ilan Aizelman WS Aug 14 '16 at 11:36
  • $\begingroup$ The last part, added after my first comment, is still utterly wrong (and neglects said comment). You should try to show this assertion you insist on including in your post, namely that $g_1(n) \cdot g_2(n) \le \max\{g_1(n),g_2(n)\}$, say, for $g_1(n)=g_2(n)=n$. Or, is the odd formula $\max\{g_1(n) \cdot g_2(n)\}$ a typo for $g_1(n) \cdot g_2(n)$? $\endgroup$ – Did Aug 28 '16 at 13:37

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.