| KinueAkachi |
O-Notation mit Beweis
Meine Frage:
Hallo zusammen, folgende Aufgabe:
long f(int n) {
long result ;
if(n < 0)
result = -1;
else {
result = 1;
for(int i=0; i < n; i++) {
int j = i+1;
result = result * j;
}
}
return result ;
}
1. Geben Sie die Zeitkomplexität T(0), T(3), T(21) der Methode f an.
2. Geben Sie eine Funktion Z(n) an, die positive n auf die Zeitkomplexität der Methode f abbildet, d.h. Z(n) = T(n) für alle n>=0
3.Geben Sie die kleinste obere Schranke für die Funktion Z(n) aus Aufgabenteil 2 in O-Notation an. Mit Beweis.
Meine Ideen:
1. T(0)= 6, T(3)= 24, T(21)= 72
2. Z(n)= 6n + 6
3. Und hier liegt das Problem. O-Notation sollte O(n) sein, aber wie beweise ich?
Danke vielmals und noch mehr, wenn ihr in der nächsten Stunde antwortet XD |
