Algorytmy - udowodnij z definicji

Question

Cześć! Mam do rozwiązania zadanie z algorytmów, znam definicje notacji dużego O, ale kompletnie nie wiem jak się za to zabrać, nie wiem czy ominęłam to na wykładach, czy o co chodzi... ale jeśli ktoś mógłby mi to wytłumaczyć, tylko tak jak dla KOMPLETNIE zielonej, będę bardzo wdzięczna!!

Zakładając, że: dla funkcji złożoności obliczeniowej f1(n) istnieje funkcja g1(n) i stała c1 spełniające warunki oszacowania w notacji dużego O ( od góry)

oraz

że: dla funkcji złożoności obliczeniowej f2(n) istnieje funkcja g2(n) i stała c2 spełniające warunki oszacowania w notacji dużego O ( od góry).

Udowodnić następującą własność: Dla funkcji F(n) = f1(n) * f2(n) oszacowanie od góry wynosi: O( g1(n)*g2(n))

~Kajkaa

 

Answer 1

Dla dostatecznie dużych n (czyli większych od jakiegoś n1), f1(n) <= c1 * g1(n)

Dla dostatecznie dużych n (czyli większych od jakiegoś n2) f2(n) <= c2 * g2(n)

Czyli dla dostatecznie dużych n (większych od maksimum z dwóch liczb (n1, n2)) zachodzi f1(n) * f2(n) <= (c1 * g1(n) )* (c2 * g2(n)) = c1*c2*(g1(n)*g2(n)) = C * (g1(n)*g2(n) gdzie C to c1*c2

Czyli f1*f2 jest O(g1 * g2)