hi, könnt ihr mir helfen f(n) zu bestimmen, sodass ich die O-Notation angeben kann?

... also habe f(n)= 2*f(n-2) gegeben, daraus habe ich diese tabelle erstellt


n --1--2--3--4--5--6--7--8---9--10---11--12
--------------------------------------------------
f(n) 1--1--2--2--4--4--8--8--16--16--32--32


... nun muss ich aus dieser tabelle schließen, wie f(n) nun von neuem aussieht.
Ich bekomme das einfach nicht hin, probiere schon seit stunden rum
wär toll,wenn mir jemand sagen könnte, was f(n) ist!

---------------------------------------------------------------------------
-------
Beispiel: ich habe f(n)=2*f(n-1) gegeben, tabelle dazu :

n --1--2--3--4---5---6-----7--- 8
--------------------------------------
f(n) 1--2--4--8--16--32---64---128

daraus kann man lesen : f(n) = 2^(n-1) ... hierdrauß kann ich dann die O-Notation rauskriegen und beweisen (mit vollst. Induktion).

Wie wäre es mit

f(n) = 2^int((n-1)/2)

dazu braucht man doch keine Stunden!

Nicht nur eine Stunde...
Ja, wie gesagt, ist die Rundung nun ein Problem. Jetzt kann ich doch nicht einfach damit weiterrechnen, bzw. durch Induktion beweisen?
Die O-Notation lautet doch O(n^2) oder`?

Wieso sollte denn Induktion hier nicht gehen?

sei f(n) = 2^int((n-1)/2) gegeben

dann ist doch:

f(n+2) = 2^int((n-1+2)/2)

daraus multiplizieren wir die 2 aus der innersten Klammer heraus:

f(n+2) = 2^int((n-1)/2+1)

da die 1 immer ganzzahlig ist, kann man die aus der int-Funktion herausziehen:

f(n+2) = 2^(int((n-1)/2)+1)

jetzt zieht man noch eine 2er-Potenz aus dem ganzen Term raus:

f(n+2) = 2 * 2^int((n-1)/2)

da aber 2^int((n-1)/2) = f(n) ist, folgt somit:

f(n+2) = 2 * f(n)


Leider habe ich "nur" Mathematik studiert und bin deshalb mit theoretischer Informatik nicht so vertraut, dass mir der Begriff "O-Notation" vertraut wäre.