Originariamente inviato da gabama
quindi per riassumere se si ha ad esempio n elementi nella lista la complessità e O (n)
Se hai solo quella struttura dati sì, altrimenti devi considerare il size anche delle altre, sempre se questo influisce sensibilmente sulla complessità di spazio relativa alla sola lista: supponiamo cioè che la tua lista mediamente abbia 30 nodi; se usi anche un array di 4-5 elementi, questo aumenta sì lo spazio occupato (ovviamente), ma non in maniera "asintotica", cioè se prima la complessità di spazio era S(N) = O(N), continuerà ad essere O(N) visto che l'aggiunta di 4 elementi, in questo caso, non cambia molto. Se invece hai (sempre per esempio) un'altra lista di size M all'incirca simile a quello della lista precedente, è più corretto scrivere che S(N) = O(N + M), sebbene poi sia pur sempre una complessità lineare.

mentre per le operazioni intendi cosa fa la funzione che opera sulla lista,nel senso le volte che si scorre la lista?
Sì, devi valutare il tempo impiegato da ciascuna operazione che compi sulla lista. Cosa fai di preciso? Inserimenti? Ricerche? Eliminazioni? Ordinamenti? Nel caso di inserimenti ed eliminazioni, i nodi interessati sono sempre quelli in fondo alla lista (o in testa) oppure si trovano in un punto particolare?

Insomma devi valutare un po' tutte queste cose. Non posso dirti nulla di più preciso, non conoscendo l'algoritmo.