|
f(1/2n) element von Theta(f(n)) |
|
Gilt für jede Funktion f(1/2n) element von Theta(f(n))?
Meine erste Idee war: ja, denn die Definition von Theta schreibt ja vor, es gibt Konstanten c0 und c1, sodass
c0*f(n) <= f(1/2n) <= c1*f(n)
Dann dachte ich vor allem an die Definition von linearen Funktionen bei denen gilt:
f(k*n) = k*f(n) mit k ist Element von R...
aber dann hab ich überlegt, gibt es auch "nicht lineare" Funktionen, bei denen das nicht gilt?
Was wäre denn so eine Funktion? Log ist ja keine lineare Funktion, oder? Wie siehts denn mit sowas aus?
__________________ I'm 71% Megatron!
|
|