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

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:
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!!