---

Geschrieben von matheFranzi1991 am 02.11.2010 um 14:54:

  Zeitkomlpexität,Speicherkomplexität

Meine Frage:
Folgendes ist gegeben

code: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: int function ( int n ) { int sum = 0; for(int i=1; i<=n; i=2*i) { for(int j=n; j>0; j--) { for(int k=0; k<2*n; k++) { sum = sum + i*(j+k); } } } return sum; }

gesucht: obere schranke, Zeitkomplexität,Speicherkomplexität

Meine Ideen:
Würde sagen weil hier das Wachstum linerar ist muss die O-Notation O(logn) sein oder sowas, hab echt keine ahnugn bitte helft mir.

---

Geschrieben von 3FingerbreitNougat am 02.11.2010 um 16:08:

 

Also Zeitkomplexität in O-Notation:

Erstes for: wird log(n) mal durchlaufen.
Zweites for wird log(n) * n mal durchlaufen.
Drittes for wird log(n) * n * 2n mal durchlaufen.

Die Obere Schranke ist ne dreifache Summenformel, zu der ich aber gerade keine Zeit hab weil ich gleich Uni muss. Werde später nochmal reinschauen.

MfG