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.