Frage zur Bedeutung von 1+o(1) bei der Landauschen klein-o Notation

Erste Frage Aufrufe: 1237     Aktiv: 11.11.2019 um 11:42

0

Diese Frage gab es mal bei einer alten Prüfung meiner Analysis Vorlesung. Wir müssen true / false ankreuzen.

Der Ausdruck links geht gegen 1/2 und somit ist O(1) erfüllt. 

Aber wie sieht es mit 1 + o(1) aus? Darf ich hier umformen, und von meinem 1/2 - 1 abziehen? 

 

Diese Frage melden
gefragt

Punkte: 0

 
Kommentar schreiben
1 Antwort
0
Ist das nicht 1+1=1. Klein o heißt doch dass das garantiert kleiner ist, big O bedeutet kleiner oder gleich. Aber konstantes Wachstum addiert ist immer noch konstantes Wachstum. Bei einer Schleife die im Kern 5 Schritte ausführt sagt man ja nicht 5 O(n), sondern O(n). O(1)+O(1)=O(1), das sollte dann für O(1)+o(1)=O(1) erst recht gelten. Vereinfacht gesagt wachsen die Kosten nicht mit der Problemgröße, sondern sind konstant.
Diese Antwort melden
geantwortet

Sonstiger Berufsstatus, Punkte: 149

 

Kommentar schreiben