En funktion, der har en operationstid på O(n); det vil sige, hvis funktionen fungerer på en samling af n elementer, funktionen måske nødt til at undersøge hvert element i samlingen, klarer op til n sammenligninger.