# Laufzeit eines Algorithmus bestimmen



## paco89 (20. Aug 2012)

hi,


```
int berechne (int n, int k){

	if(n==0){
	return k;
	}

	int value = berechne (n/3, k);

	if(n<42){
	
	for (int i = 0; i<k*k; i++){
	value +=i*n;
	value += berechne(n/3,k) +2 ;
	}
	else{
	for(int i = 0 ; i<n; i++){
		value += i*n;
		value += 3*berechne(n/3, k) + 3;
	}
	}
	}
	return value;
}
```


davon habe ich auch die musterlösung (siehe Musterlösung). allerdings verstehe ich da nicht woher das "n" im letzten fall T(n)= 2T(n/3) + n + c kommt. ich hatte nämlich nur T(n)= 2T(n/3) + c .


----------



## SlaterB (20. Aug 2012)

die Schleife in Zeile 18 läuft doch n mal, da kann man das n schon irgendwie aufnehmen,
zumal das im Lösungstext auch ziemlich klar begründet wird?

genau 2x T(n/3) verstehe ich wiederum nicht, 
zwar taucht berechne(n/3, k) genau 2x in den betrachteten Code-Abschnitten auf, aber in der Schleife wird es doch n-mal berechnet..

T(n)= n * T(n/3) + c . 
schon eher, vielleicht immer noch + n, sonst kürzt sich das in der Auflösung alles weg wenn nur noch konstant c da ist..

berechne(n/3, k) könnte man schließlich auch einmalig vorberechnen, dann wäre es nur noch 1x statt 2x?
wie man sieht bringe ich eher mehr Fragen als Antworten hinein


----------



## paco89 (20. Aug 2012)

nein, eigentlich nicht....dass mit n als Anzahl der schleifendurchläufe, hatte ich in dem Zshg. schon gedacht.


----------

