EFFICIENZA ALGORITMI

Salve!

Ho iniziato questo mese il corso di strutture dati, e da subito ci è stato insegnato a ottimizzare ogni programma in C che svolgiamo, minimizzando prima di tutto il tempo di esecuzione, poi lo spazio occupato in memoria.

Bene, in una slide in cui si calcola i passi di un algoritmo c'è scritto:

sum=0; [1 passo]
for (i=1;i<N;i++) [$2*N$ passi$]
for (j=i;j<N;j++) [$2*(sum_{i=1}^N (N+1-i))$ passi]
sum=sum+1; [$sum_{i=1}^N (N+1-i)$ passi]
return sum; [$1$ passo]

Si calcolano i passi (unità di tempo necessari alla compilazione di un algoritmo. Ma ci sono diversi punti oscuri.. Perchè mai il primo for ha $2*N$ passi, perchè il secondo for ne ha $2*sum_{i=1}^N (N+1-i) $, perchè l'argomento della for ha $sum_{i=1}^N (N+1-i)$ istruzioni?
Non riesco a capire come si contano questi passi...

E' un argomento che mi mette un po' in difficoltà...

Nobody can help me?

Il calcolo dei passi è semplice, se si ha presente come viene eseguito un ciclo enumerativo di tipo FOR, il quale comporta, ad ogni "giro", la verifica della condizione di uscita e l'incremento dell'ìndice associato.
Pertanto, il FOR esterno esegue N volte il controllo su $i<N$ e l'incremento dello stesso indice con $i++$: in totale $2*N$ passi.
Il ciclo nidificato esegue il controllo $j<N$ e l'incremento $j++$ per $N-i+1$ volte (j infatti parte da i e arriva a N): in totale $2*(N-i+1)$ passi.
Considerando che questi $2*(N-i+1)$ passi vanno eseguiti per ogni i compreso tra 1 ed N, si ottiene la sommatoria indicata $sum_{i=1}^N2*(N+i-1)$.
Analogamente per l'istruzione sum=sum+1, che è compresa nel ciclo nidificato: è eseguita $N-i+1$ volte nel ciclo su J, per ogni i compreso tra 1 e N.
Ciao

Ah ok ti ringrazio...