+1 Daumen
136 Aufrufe

function A(n,a):
if n = 0 then
   return a
fi
x := A(n /2,1) + A(n/2,2) + A(n/2,3)
for i = 1 to n do
    x := x + 1
od
return x


Ich soll das asymptotische Wachstum in Theta Notation angeben für die Laufzeit.


Meine Überlegung:

1. Idee:
mastertheorem
a= 3 b=2 c=1
3 > 2^1=2
somit t(n) \in Theta ( n^(log3/log2) = n^(log_2 3)

Kann mir jemand sagen, ob das stimmt?

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community