0 Daumen
913 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!!

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.

von 2,5 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
0 Antworten
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community