Spiegazione del perché utilizziamo le sommatorie per valutare il costo computazionale

[notedo]

🚨giuro che la finisco🚨

Ciao a tutti, il motivo per il quale sto scrivendo questa guida è che ho passato ore a cercare di capire come funzionasse il meccanismo della sommatoria per il calcolo della complessità di un algoritmo, e dopo averlo capito, voglio farti risparmiare le ore che ci potresti mettere a capirlo.

Il problema

Cerchiamo di comprendere il problema alla base. Prendiamo come esempio questo ciclo for:

def func1(n)
    count = 0
    for i in range(n):
        count += i

è facile notare che ogni volta che i aumenta di 1, il nostro count aumenta di 1. Ora proviamo a riscrivere matematicamente la stessa cosa: $\sum\limits_{i=1}^n\text{count}$. Inizia a notare la somiglianza? Facciamo ora un passo avanti e cerchiamo di capire il meccanismo dietro: dietro a un ciclo for o a un ciclo while in cui il passo aumenta (ad esempio i) c'è una sommatoria implicita.

I cicli annidati

Una delle difficoltà maggiori che ho avuto è stata quando dovevo calcolare la complessità dei cicli annidati, perché in alcuni come l'es6 di: #3 non moltiplicavo la complessità del ciclo esterno per quello interno, mentre in altri si.
Quando si presentano davanti a noi uno o più cicli annidati, dobbiamo capire due cose:

• L'esecuzione dei vari cicli dipende dalle stesse cose (ad esempio una i che viene incrementata e usata in entrambi i cicli) o no?
• Se l'esecuzione dei vari cicli non dipende dalle stesse cose, quante volte eseguo questi cicli?
  Prendiamo questo pseudocodice: