# O- Notation, Frage zu Codeschnipsel (Peseudocode)



## sh33p (4. Jul 2010)

ich habe einen kleinen Codeschnipsel und möchte anhand der O-Notation die Laufzeit abschätzen. Die Laufzeit soll hier O(n) sein. Begründung ist: "Weil die maximale Rekursionstief n+1 ist".
Kann mir das jemand mal bitte erklären?
(ein block stellt eine Methode dar)

[Java] 

block bhochn(ein: b € N, n € N aus: erg € N)
{
falls n = 0 dann{
erg <- 1;
} sonst{
bhochn(b,n-1, erg);
erg <- erg*b;

}

} 

[/code]


----------



## XHelp (4. Jul 2010)

Naja, du berechnest ja b^n
b^5 wären b*b*b*b*b, daher "n" Schritte.
+1 kommt durch den Rekursionsabbruch 
	
	
	
	





```
falls n = 0 dann
```
, sprich du würdest 5 mal die Rekursion durchlaufen, dann das 6. mal starten und es kommt zum Abbruch


----------



## sh33p (4. Jul 2010)

wie sieht es mit diesem algorithmus aus? eine andere variante bhochn auszurechnen.
hier soll die laufzeit O(log n) sein.
oberes beispiel kann ich mittlerweile nachvollziehen.


```
block bhochn(ein: b € N, n€ N, aus: erg€ N)
{
falls n= 0 dann {
erg <-1;
} sonst{
falls n mod 2 = 0 dann {
bhochn(b*b, n div 2, erg);
} sonst{
bhochn(b,n-1,erg);
erg <- erg*b;
}
}
}
```


----------



## XHelp (4. Jul 2010)

du rechnest die zahl immer durch 2.
log_2(x) gibt dir an die oft du die zahl durch 2 Teilen kannst, oder anders gesagt:
a^b=x
log_a(x)=b


----------



## sh33p (4. Jul 2010)

ah so langsam steig ich dahinter.wenn ich noch ne frage habe melde ich mich.

danke erstmal


----------



## sh33p (4. Jul 2010)

man könnte doch sagen,dass die laufzeit 2*ld n wäre, da bei jedem 2. durchlauf halbiert wird.
da es in der O-Notation keine Konstanten gibt, ist es einfach O(log n)
?!


----------



## XHelp (4. Jul 2010)

Öhm, ich denke schon, wobei da noch das "+1" ist wegen dem rekursionsabbruch.


----------

