Komplexität in O-Notation

[Tachyon]

Ich bin gerade in der Situation, die Komplexität eines einfachen Algoritmus von mir bestimmen zu müssen. Dabei handelt es sich um einen Frequenzmischer, der formal mit der nachfolgenden Formel beschrieben ist:
$\tilde{x}(k) = \sum^{N-1}_{k=0}x(k)\cdot e^{-j2\pi\frac{f}{f_{A}}k}$
Meiner Meinung nach müsste die Komplexität hier O(N) betragen. Da ich allerdings nie sicher bei der O-Notation war, frage ich hier lieber nochmal nach, ob ich da richtig liege.
PS: Wenn das hier eher in die Mathematik-Sparte gehört, bitte verschieben.

[Gast]

Was der Frequenzmischer genau macht, ist nicht relevant. Du musst dir eine Elementaroperation aussuchen, die du messen willst. Bei der schaust du dann, wie oft du diese Elementaroperation in Abhängigkeit von N machst.

Das setzt voraus, dass du einen konkreten Algorithmus (also eine Abfolge von Anweisungen, blablabla) hast, und nicht die Formel, die einen Frequenzmischer formal beschreibt.. Falls der Algorithmus nur darin besteht, diese Formel auszuwerten, würde ich auch O(N) sagen, da du genau N-mal einen Ausdruck auswertest. Hilfreich ist es bei so etwas auch immer, sich anzusehen wie viele Schleifen du schachtelst, scheint hier eine mit O(N) zu sein.

[Tachyon]

Die Anzahl der Iterationen lässt sich direkt aus der Formal ableiten. Dann werde ich wohl mit O(N) richtig liegen. Danke.

[ghgshh]

Tachyon schrieb:

Die Anzahl der Iterationen lässt sich direkt aus der Formal ableiten. Dann werde ich wohl mit O(N) richtig liegen. Danke.

1. Es kommt auf die Implementierung an!
2. Hier wäre \Theta(N) angebrachter als O(N)

[fr4ger]

wenn x(a), f und f_a auch von k abhängen, wäre ich mir nicht so sicher.
tun sie das?

[Tachyon]

Nur k und x(k) sind variabel. Alles andere ist konstant. Bei x(k) handelt es sich um eine einfache Indizierung eines Array-Elements.