Ich wollte fragen, ob meine Vermutung zur Laufzeit passen.
function A1(n):
if n ≤1 then return 1
fi
x := A1(⌊n/2⌋)+A1(⌈n/2⌉)
y :=0
for i =1 to x do
y := y +1
od
return y
Da x = n ist (wegen ⌊n/2⌋+⌈n/2⌉ = n), hat die for Schleife eine Laufzeit von Theta(n).
function A2(n):
if n ≤1 then return n
fi
x := A2(n−1)
y :=1
for i =1 to ⌊√n⌋ do
y := y +1
od
return x+y
Das heißt x wird n Mal aufgerufen und die for Schleife ist in O(n), deshalb sage ich hier auch Theta(n).
function A3(n):
x :=0;
for i =1 to n do
for k = i−3 to 2i do
for l= k to max{i,k +3} do
x := x+1
od
od
od
return x+A3(⌊n/2⌋)
Die drei Vorschleifen habe eine Laufzeit von O(n^3) und da n immer halbiert wird mit jedem Aufruf, sage ich Theta(n^3 log n).
Hoffe es passt so:) Danke im Voraus:D
