0 Daumen
2,1k Aufrufe

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)  ∑n j=1(ti - 1)

blob.png

Danke!!

Avatar von

Was bedeutet ← ?

1 Antwort

0 Daumen

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.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community