Laufzeitanalyse

RiceBall

Hi Leute,
Ich soll bei dem folgenden Programmcodeausschnitt erklären, was es macht und die Laufzeit dazu berechnen. Jedoch scheitert es bereits bei dem Erkennen der Aufgabe des Programms.

int Pow2(int n)
 {
 if (n > 0){
 return (Pow2(n-1) + Pow2(n-1));
 }
 else {
 return 1;
 }
 }

Was ich sehe, ist, dass es wohl gar nichts berechnet, sondern einfach nur Pow2 aufruft und zwar jedes mal mit n-1, bis n=0. Also effektiv macht das Programm doch gar nichts. Und wegen der Laufzeit, so ruft sich das Programm doch selbst N mal auf, aber das ganze 2x weil man 2x Pow2 hat. Also sähe die O-Notation doch am Ende so aus: O(2*n)=O(n).
Was sagt ihr dazu? Danke schon mal für eure Hilfe.
mfg
RiceBall

Diese Pow2 geben auch einen Wert zurück und damit wird gerechnet.

Pow2(1) = Pow2(0)+Pow(0) = 1 + 1 = 2

Pow2(2) = Pow2(1)+Pow(1) = Pow2(0)+Pow(0) + Pow2(0)+Pow(0) = 1+1 + 1+1 = 2 + 2 = 4

Pow2(3) = Pow2(2)+Pow(2) = (wir wissen jetzt das Pow2(2) 4 ist) = 4 + 4 = 8
...

Und Pow2 wird 2 mal in Pow2 aufgerufen.

RiceBall

ach jaaa.... pow2(0) hab ich außer Acht gelassen. Jetzt macht das ganze auch Sinn und ich kann daimt arbeiten...^^. Vielen Dank für die Hilfe.