Matematicamente.it

In questo algoritmo non capisco la complessità $O(n+k)$, in particolare se terzo for non ci fosse la complessità dell'algoritmo sarebbe ugualmente $O(n+k)$ ?
La complessità non dovrebbe essere $O(max(n,k))$ che a mio avviso non è la stessa cosa di $O(n+k)$,
dove sbaglio?

zio_mangrovia ha scritto:$O(max(n,k))$ che a mio avviso non è la stessa cosa di $O(n+k)$

https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Ciao!

probid ha scritto:https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Grazie 1000.
Ma il terzo for preso da solo ha complessità $O(k)$ ? E' corretto?

zio_mangrovia ha scritto:

probid ha scritto:https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Grazie 1000.
Ma il terzo for preso da solo ha complessità $O(k)$ ? E' corretto?

No. Devi ragionare sul while. La somma dei valori dell'array C è uguale a \(n\), quindi quel while è vero per \(n\) volte ed è falso per \(k\) volte (ad un certo punto diventa falso ed esce dal ciclo).

vict85 ha scritto:No. Devi ragionare sul while.
La somma dei valori dell'array C è uguale a \(n\)

Questo è ok.

quindi quel while è vero per \(n\) volte ed è falso per \(k\) volte (ad un certo punto diventa falso ed esce dal ciclo).

Non mi torna tanto...
Il while è vero per \(n\) volte però solo complessivamente: per ogni iterazione del for il while può essere vero ma per un numero limitato di valori che può non essere \(n\)

k=4
n=10
i=0 while vero per 1 volte
i=1 while vero per 0 volte
i=2 while vero per 4 volte
i=3 while vero per 5 volte
i=4 while vero per 0 volte

E' vero che alla fine complessivamente ho \(n\) iterazioni ma anche \(k\) dettate dal for, no?
Allora qual è la complessità di quest'ultima parte ?

Quello che intendevo è che la condizione del while viene calcolata complessivamente \(n+k\) volte, di cui n vere e k false.