# Laufzeitanalyse



## hallowelt543 (25. Nov 2018)

```
function A(n,a)
if n = 0 then
return a
fi
x := A(\lfloor n/2 \rfloor,2) + A((\lfloor n/4 \rfloor),1)
for i = 1 to n do
x := x + 1
od
return A(\rfloor n/8 \rfloor,2) + x
```

Die Aufgabe sagt, dass ich zeigen soll in was für ein Theta es liegt.
Ich habe direkt an das Mastertheorem gedacht.
Meine Überlegung:
a= 3 weil es ja 3 rek. Aufrufe sind
b= hier weiß ich es nicht weil einmal n/2, n/4 und einmal n/8 ist... was kann also b sein?
f(n) bzw. c muss ja einfach 1 sein


----------

