Wie beweise ich f(n)=O(f(2n))?

Question

Wie beweise oder wiederlege ich f(n)=O(f(2n))?

Comments

Das hängt vom konkreten f ab.

---

f(n) ist eine beliebige
reellwertige positive Funktion mit nat ürlichen Zahlen als Argument.

sorry das ist untergagen.

Answer 1

f definiert durch f(2n)=0 und f(2n+1)=1 ist ein Gegenbeispiel.

Comments

kannst du das nochmal genauer erklären ich verstehe es nicht was meinst du mit f ist definiert als f(2n) = 0 und f(2n+1)=1 damit wär doch f(2n) trotzdem noch eine obere schranke von f(n) da f(n) auch gleich null oder verstehe ich da was falsch?

---

zusatz und f(2n+1) >= f(n) und somit auch eine obere schranke von f(n) .

---

Wie soll denn 0 eine obere Schranke von 1 sein? Es ist 1>0. Die Def. nochmal in anders: f(n)=0 falls n gerade und f(n)=1 falls n ungerade.

---

Ah jetzt verstehe ich was du damit gemeint hast. :)
Aber noch eine frage die Funktion soll ja Positiv sein und ic dachte das bedeutet f(n)>0.
aber wenn ich deine Definition der funktion nehme ist sie doch nicht mehr echt größer als 0.

---

Dann nimm halt: f(2n)=1 und f(2n+1)=2n+1