Originariamente inviato da 5t4rdu5t
ho un dubbio sulla coplessità asintotica riguardante la lista semplice nella operazione di inserimento ordinato. Da quello che ho capito dovrebbe essere O(1) se l' inserimento si fa in testa oppure O(n) se bisogna fare di volta in volta i confronti.
Un altro dubbio è sulla ricerca... io penso sia sempre O(1) e O(n), ho fatto un ragionamento giusto?
L'inserimento in una lista collegata ordinata è in O(n) nel caso peggiore (e direi anche in quello medio), mentre nel caso migliore come dici si è in O(1) ma è poco significativo, non entra nemmeno in gioco l'ordinamento.

Anche ricerca è in O(1) nel caso migliore e O(n) negli altri, però specifica di quale caso stai parlando altrimenti non è molto preciso dire "io penso sia sempre O(1) e O(n)"; quando non si specifica ci si riferisce solitamente al caso peggiore.