Een functie die een bewerkingstijd van O(n) heeft; dat wil zeggen, als de functie op een verzameling van n items werkt, wellicht de functie te onderzoeken van elk item in de collectie, uitvoeren tot n vergelijkingen.