Quando possibile (e in questo caso lo e') sarebbe meglio utilizzare la notazione theta anziche' O grande.

Originariamente inviato da Scara95
O(n) é solo il caso peggiore, che poi possa essere frequente un numero vicino a questo é un'altro discorso.
Direi che anche il caso medio e' in O(n) se non c'e' nessuna particolare probabilita' da considerare, visto che il numero di operazioni resta lineare al numero di elementi.

Originariamente inviato da 5t4rdu5t
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)



penso sia lo stesso ragionamento per l' inserimento...
Direi di si, comunque se stai studiando all'universita' o altrove e non hai ancora trattato il caso medio puoi tranquillamente non specificarlo per il momento.

Per l'inserimento la complessita' e' la stessa della ricerca semplicemente perche' fai le stesse operazioni della ricerca piu' l'inserimento, che puoi fare in tempo costante.

Originariamente inviato da LeaderGL
scusate ma come può un algoritmo di inserimento ORDINATO avere un caso migliore di O(1) ed uno peggiore di O(n) ??

Per avere O(1) significa che inserisci "dove capita"...e di conseguenza non hai la certezza di un inserimento ORDINATO.
Pur volendo mantenere la struttura ordinata, nel caso migliore (lista vuota, minore del primo elemento o altro, dipende dai test effettuati nell'algoritmo) l'inserimento e' indipendente dal numero di elementi presenti nella struttura dati, per questo lo classificherei come O(1).

Inserire in tempo costante non significa necessariamente inserire a casaccio.