Bisogna specificare varie cose:
1) struttura dati
2) tipo di ordinamento

però in linea generale per effettuare un inserimento ordinato (e quindi inserire dei numeri in un vettore,lista,albero,heap,etc) si può arrivare ad affermare che nel caso migliore l'inserimento ha una complessità di O(1).

Il caso migliore si verifica quando gli elementi da inserire sono già ordinati dal più grande al più piccolo. Perchè l'unico confronto da fare è "elemento_da_inserire <= primo_elemento", la risposta sarà SI e quindi si fa un unico confronto e si inserisce l'elemento in testa.

Tutto il resto (caso medio e caso peggiore) dipendono dall'algoritmo utilizzato. Il miglior algoritmo per effettuare un ordinamento (e quindi anche un inserimento ordinato) ha come caso medio e come caso peggiore O(n log n). Non si scende al di sotto.