[Algoritmi] Problema analisi algoritmi

[fabixus]

Salve a tutti,
Sto studiando il corso di introduzione agli algoritmi, riesco a capire come funzionano gli algoritmi, ma ho un problema riguardo alla loro analisi, non riesco proprio a capire come applicare la matematica a questi algoritmi.

Faccio l' esempio dell'insertion sort preso dal libro Introduzione agli algoritmi di Cormen

Insertion-Sort( A[] ) 
1    for j = 2 to A.length               
2        key = A[j]
3        i = j + 1
4        while i > 0 and A[i] > key
5            A[i + 1] = A[i]
6            i--
7        A[i + 1] = key

il libro dice che lil while interno è $\sum_{j=2}^n t_j$ , la mia domanda è come è arrivato a usare la sommatoria per quel ciclo? Perchè usiamo le sommatorie per i cicli interni?

Grazie in anticipo

[apatriarca]

Usiamo le sommatorie per qualsiasi ciclo.. Il tempo totale di esecuzione di un ciclo è infatti uguale alla somma di quello di ogni iterazione. In questo caso però stai considerando il ciclo for e non il ciclo while.. Stai infatti sommando su \(j\) che va da \(2\) a \(n\) come il ciclo for. \(t_j\) è invece probabilmente il tempo del ciclo più interno. Questo tempo non è costante (dipende dal particolare array).