Informatiker Board | Druckvorschau: f(1/2n) element von Theta(f(n))

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- f(1/2n) element von Theta(f(n)) (http://www.informatikerboard.de/board/thread.php?threadid=319)

Geschrieben von JROppenheimer am 23.11.2007 um 11:18:

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?

Geschrieben von Tobias am 23.11.2007 um 11:51:

Wie soll das geklammert sein?

f(1/2*n) = f(0.5 * n) oder f(1/(2*n)) = f((2*n)^(-1))

Geschrieben von JROppenheimer am 23.11.2007 um 11:56:

sorry, f(0.5*n)

Geschrieben von Tobias am 23.11.2007 um 12:32:

Bei linearen Funktionen stimmt das selbstverständlich. Bei anderen Funktionen geht es manchmal, manchmal nicht.

Wie es bei $[latex]f(n) = \log(n)[/latex]$ aussieht findest du selbst raus. Außerdem kannst du noch eine Reihe anderen Funktionen untersuchen:

[latex]f(n) =n![/latex]

...