Landau - O-Notation < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | f [mm] \in [/mm] o(g) [mm] \Rightarrow 2^f \in o(2^g)
[/mm]
wobei
[mm] 2^f(n) [/mm] := [mm] 2^{f(n)}
[/mm]
f und g sind total |
Hallo,
o.g. Aussage soll bewiesen werden.
Also, es gilt f [mm] \in [/mm] o(g).
Das heißt [mm] \forall [/mm] c . [mm] \exists n_0 [/mm] . [mm] \forall [/mm] n > [mm] n_0 [/mm] . c*(f(n)+1)<g(n)
Wie komme ich nun daraus auf
[mm] d*(2^f(n)+1)<2^g(n)
[/mm]
was ja [mm] 2^f \in o(2^g) [/mm] entspricht.
Kann mir jemand einen Tipp geben, oder setze ich sowieso falsch an?
Danke,
Anna
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Mo 21.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
