Originariamente inviato da Kaamos
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.
allora devo specificare in qst modo?
l' inserimento nel caso migliore è O(1) perchè se tratta dell inserimento in testa indipendentemente dal numero di nodi della lista, O(n) perchè bisogna scorrere tutta la lista quindi caso peggiore e caso medio(anche se caso medio non l' ho capito tanto bene)

Originariamente inviato da Kaamos
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.
penso sia lo stesso ragionamento per l' inserimento...