[Algoritmi]Analisi complessità di un algoritmo

[Skeggia1]

Ciao a tutti.
Devo valutare la complessità in termini della notazione $Theta$ ed in funzione di n del seguente algoritmo:



Gli assegnamenti della prima riga costano tempo $Theta(1)$. Il ciclo for interno viene eseguito n volte per cui $Theta(n)$. Mentre per quanto riguarda il ciclo while, dopo una prima iterazione $t=1$ e $k=1$, dopo una seconda $t=2$ e $k=3$, dopo una terza $t=3$ e $k=6$, dopo una quarta $t=4$ e $k=10$ allora possiamo dedure che $k=(t+t^2)/2$.
Io ho pensato che se fissiamo una taglia $n$, quando usciamo dal ciclo while $k>n$ allora $(t+t^2)/2=n ~= t^2=n rArr t=sqrt(n)$ e quindi la complessità del blocco while è $Theta(sqrt(n))$.
Infine la complessità, in funzione di n sarà$T(n)=Theta(n*sqrt(n))$.

Questo è il punto cruciale, poiché non riesco a definire diversamente k, volevo chiedervi, se innanzitutto il mio modo di operare è giusto?
Grazie.

[Rggb1]

L'impianto mi sembra corretto, però direi che il ciclo while ha costo $Theta (sqrt(n \/ 2))$ - al solito attendo conferme/smentite.

[apatriarca]

Supponendo per comodità che \(n\) sia un numero triangolare, il numero di iterazioni del while è la soluzione intera dell'equazione \( t^2 + t - 2\,n = 0 \) più uno (se non sbaglio è necessario aggiungere uno perché c'è il \(\leq\) ma non ci ho pensato più di tanto). Cioè
\[ t = \frac{ \sqrt{ 8\,n + 1} - 1 }{2} + 1 \sim \sqrt{2\,n}. \]
Il ciclo while (ignorando il costo delle istruzioni interne) è quindi certamente \( \Theta\bigl(\sqrt n\bigr) \) e la complessità generale è \( \Theta\bigl(n\,\sqrt n\bigr) \) come avevi già calcolato.

@Rggb: \( \Theta\Bigl(\sqrt{ n/2 }\Bigr) = \Theta\bigl(\sqrt n\bigr) \ldots \)

[Skeggia1]

Ok, grazie mille a tutti!!

[Rggb1]

"apatriarca":@Rggb: \( \Theta\Bigl(\sqrt{ n/2 }\Bigr) = \Theta\bigl(\sqrt n\bigr) \ldots \)

Certo, la mia era solo una precisazione.

Il mio errore è nel calcolo è corretto $sqrt(2n)$ e non $sqrt(n \/ 2)$.