Komplexität / O-Notation

[*CMAN* 0]

Hallo liebe Mitglieder,

wie ermittle ich die Komplexität richtig?
Gegeben ist eine for-Schleife, die die Komplexität O(n) hat,
sowie zwei Funktionen (jeweils O(n)), die in der Schleife aufgerufen werden.

for(i=1; i<=n; i++) { //O(n)
funk1(); //O(n)
funk2(); //O(n)
}

1.Version
-Schleifeninnere:
O(n) + O(n) = O(n)
-Schleife:
O(n)
-->ergibt: O(n)*O(n) = O(n^2)

2.Version
- Schleifeninnere:
O(n) * O(n) = O(n^2)
- Schleife:
O(n)
-->ergibt: O(n^2) * O(n) = O(n^3)

Welche der beiden Versionen ist richtig?

Über eine Antwort würde ich mich sehr freuen.

Vielen Dank und viele Grüße

[Gast]

Die 1. Version ist richtig.

[*CMAN* 0]

@Tim
vielen Dank für deine Hilfe!!!
das bedeutet also das die Aufrufe innerhalb einer Schleife immer addiert werden?!

[otze]

ja natürlich. Du rufst ja immer einmal funk1() UND funk2() auf. nicht wie bei der Schleife "n MAL Schleifenrumpf"

[rage_quit]

wieso ists nicht (2*n)^2?

@edit axo n = fn1 + fn2 ?:)

[Walli]

du hast die

Landau-Symbole verstanden!

[*CMAN* 0]

danke, also version 1

habt mir super geholfen!
danke