Ci si picchia sul caso migliore che e' praticamente inutile!

Originariamente inviato da Who am I
Non mi è chiaro cosa intendi per "inserimento ordinato".
Non basta questo termine per far capire cosa hai in mente tu.
Se intendi l' inserimento in un vettore ordinato, la complessità è O(log N) nel caso peggiore e O(1) nel caso migliore.
Però bisogna che ti spieghi meglio.
Ha parlato di lista semplice (quindi deduco lista concatenata semplice), e se parla d'inserimento ordinato suppongo ci sia una relazione d'ordine totale sull'insieme su cui si lavora, non ho capito cosa e' ambiguo.

Originariamente inviato da LeaderGL
Non può essere O(1) perchè altrimenti significherebbe che la complessità degli algoritmi di ordinamento può essere O(1) e non è così.

Deve essere come minimo O(n), perchè i confronti li devi fare!
E' un inserimento non un ordinamento, quindi puo' essere O(1) nel caso migliore...
Se la lista e' vuota che confronti possiamo fare? Hai specificato nel tuo ultimo post quello che intendevo io.

EDIT: doppio post, pardon