Aby udowodnić lub obalić dane zapisy asymptotyczne - wielka, złożoność-teoria

1) maks{f (n), g (n)} = O(f (n) + g (n)), gdzie f (n) ig (n) są funkcjami dodatnimi.

2) min{f (n), g (n)} = Ω(f (n) + g (n)), gdzie f (n) ig (n) są funkcjami dodatnimi.

Moim dowodem na pierwsze pytanie jest coś w rodzaju: maks {f (n) + g (n)} byłoby> niż f (n) + g (n). Więc ustawienie stałej c na maks {f (n) + g (n)} sprawi, że Wielki „warunek O” zostanie wstrzymanyprawdziwe. Czy to właściwy sposób, aby to zrobić? Ponadto nie jestem pewien, jak dalej udowadniać drugie pytanie, więc wszelka pomoc w tym zakresie byłaby bardzo mile widziana.

Odpowiedzi:

Pierwszy jest poprawny. Tak jak max(f(n),g(n)) < f(n) + g(n). Drugi jest nieprawidłowy. Możesz to pokazać zgodnie ze standardem. Przypuszczać f(n) = log(n) i g(n) = n. Widzimy to min(f(n),g(n)) = log(n) ale wiemy to log(n) nie jest Omgea(n + log(n)).