Линеарно време
У теорији комплексности, за алгоритам се каже да захтева линеарно време, или O(n) време, ако је асимптотска горња граница времена његовог извршавања пропорционална величини улаза, која се обично означава словом n.
Неформално, време извршавања алгоритма се повећава линеарно са порастом величине улаза. На пример, процедура која сабира све чланове низа захтева време пропорционално дужини низа. Овакав опис је помало нетачан, јер време извршавања може знатно да одступа од тачне пропорционалности, посебно за мале вредности n. За више информација, погледати чланак нотација великог О.
Линеарно време се често сматра пожељном особином алгоритма. Улажу се велики напори у дизајн алгоритама чије време извршавања је блиско линеарном времену или краће. У ова истраживања улазе и софтверски и хардверски методи. У случају хардверских метода, неки алгоритми, који математички узев, никад не могу да постигну линеарно време са стандардним моделом израчунавања, се извршавају у линеарном времену. Постоје разне хардверске технологије које користе паралелизам да омогуће ово.