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!