TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 5

• Beweisen oder widerlegen Sie, dass für beliebige positive Funktionen f(n) und g(n) die Beziehung f(n) = $\Theta$(g(n) $\rightarrow$ f(n) = O(3g(n)/2) gilt. Beachten Sie, dass ein Beispiel kein Beweis, ein Gegenbeispiel aber sehr wohl eine Widerlegung ist!
• Beweisen oder widerlegen Sie die nachstehende Behauptung:

f(n) = $\Omega$(g(n)) $\land$ g(n) = $\Omega$(h(n)) $\rightarrow$ f(n) = $\Omega$(h(n))