Notacja theta

ogre · Post autor: **ogre** » 1 paź 2013, o 10:13

\(\displaystyle{ f(n), g(n)}\) - funkcje asymptotycznie nieujemne (dla duzych n)
Udowodnic \(\displaystyle{ max(f(n),g(n)) = \theta (f(n)+g(n))}\) uzywajac def.

Definicję znam, ale nie wiem jak zacząć takie zadania.

yorgin · Post autor: **yorgin** » 4 paź 2013, o 16:54

Masz dobrać takie stałe \(\displaystyle{ A, B}\), aby spełniona była zależność

\(\displaystyle{ A(f(n)+g(n)) \leq \max\{f(n),g(n)\}\leq B(f(n)+g(n))}\)

dla \(\displaystyle{ n}\) dostatecznie dużych.

Jedna ze stałych jest za darmo. Która?

liu · Post autor: **liu** » 4 paź 2013, o 21:55

Poza tym, to jest duże \(\displaystyle{ \Theta}\).