Kurs:Algorithmen und Datenstrukturen/Vorlesung/Theta-Notation




-Notation

Bearbeiten

Die exakte Ordnung   von f(n) ist definiert als:

 

Oder etwas kompakter:

 

Anschaulich formuliert bedeutet das, dass   die Menge aller durch f nach unten und oben beschränkter Funktionen und somit die asymptotische untere und obere Schranke ist.

Zu zeigen:  


 

Zeige  

  •  

 

 

 

Beispiel 1

Bearbeiten

Wir stellen uns die Frage, ob   bzw. ob   eine obere Schranke für   ist. Die Antwort ist ja. Die Begründung dazu lautet folgendermaßen:

 

 

 

Beispiel 2

Bearbeiten

Wir stellen uns die Frage, ob   bzw. ob   eine obere Schranke für   ist. Die Antwort ist nein. Beweisen kann man das durch Widerspruch. Unsere Annahme ist:  

 

 

Wähle   Widerspruch!!