Laufzeitanalyse Algorithmus O-Notation bestimmen

Question

wie muss ich vorgehen?

Ich muss für beide Funktionen groß O definieren..

Ich habe für:  f(n) O(n-1/2) und für

g(n)  ∑ⁿ _j=1(t_i - 1)

Danke!!

Comments

Was bedeutet ← ?

Answer 1

f ist logarithmisch, weil bei jedem Rekursionsschritt die Eingabe halbiert wird und ein Funktionsaufruf bis auf die Rekursion konstante Zeit benötigt.

Ich vermute, ← soll eine Zuweisung sein. Dann ist g linear. Zwar wird auch hier die Eingabe bei jedem Rekursionsschritt halbiert, aber die while-Schleife braucht anfangs n/2 Iterationen, dann n/4 Iteration, dann n/8 Iteration u.s.w.