Lineaire tijd
In de computationele complexiteitstheorie kan een algoritme in lineaire tijd of O(n) worden uitgevoerd als de benodigde tijd lineair afhangt van de omvang van de invoer. Ieder algoritme heeft een bepaalde complexiteitsgraad, dus dat kan lineaire tijd zijn. Voorbeelden hiervan zijn het optellen van een lijst van gehele getallen, het opzoeken van een letter in een string of het uitvoeren van een bewerking in constante tijd op alle knopen in een boomstructuur. Bij het tweede voorbeeld is het niet noodzakelijk dat de hele invoer wordt doorlopen, want als de letter aan het begin van de string staat is het algoritme eerder klaar. Dit is volgens de definitie van O(n) toegestaan, aangezien de tijd van het algoritme door een lineaire functie wordt begrensd. De andere twee voorbeelden vereisen dat de gehele invoer wordt doorlopen, deze zijn behalve O(n) ook Ω(n) en daarmee dus Θ(n).
Ieder probleem waarbij de gehele invoer nodig is om het antwoord te berekenen vereist ten minste lineaire tijd aangezien het doorlopen van de invoer in lineaire tijd verloopt. Een ander voorbeeld van een O(n) algoritme is lineair zoeken, een zoekalgoritme dat mogelijk alle elementen in een lineaire datastructuur, meestal een lijst, doorloopt. Verondersteld dat n het aantal elementen in de datastructuur is, is de tijd die nodig is om een bepaald element te vinden lineair afhankelijk van n. Daar komt de naam lineair zoeken vandaan.