Originariamente inviato da Kaamos
L'algoritmo è iterativo quindi è sufficiente calcolare quante volte viene eseguita l'operazione dominante, che è quella all'interno del for. Il ciclo interno effettua Θ(n) iterazioni, mentre in quello esterno t e k crescono informalmente così:

t k
0 0
1 1
2 3 = (2+1)
3 6 = (3+2+1)
4 10 = (4+3+2+1)
5 15 = (5+4+3+2+1)
6 21 = (6+5+4+3+2+1) = (6*7)/2

k ogni volta vale la sommatoria di i che va da 1 a t, che vale (t*(t+1))/2. Il while termina quando k vale n (in realtà quando supera n, ma asintoticamente non cambia nulla), cioé quando:

n = k = (t*(t+1))/2

Faccio prima a linkare wolfram che a tentare di scrivere le formule in maniera comprensibile:
http://www.wolframalpha.com/input/?i...+%3D+0+solve+i

La soluzione in funzione di n (quella "positiva", l'unica accettabile in questo contesto) è in Θ(√n), quindi l'algoritmo dovrebbe essere in Θ(n√n).

Però aspetta la conferma (o la smentita) di qualcuno più bravo di me in matematica.
In attesa della conferma, ti ringrazio per la risposta chiara Kaamos