Linearno vreme
U teoriji kompleksnosti, za algoritam se kaže da zahteva linearno vreme, ili O(n) vreme, ako je asimptotska gornja granica vremena njegovog izvršavanja proporcionalna veličini ulaza, koja se obično označava slovom n.
Neformalno, vreme izvršavanja algoritma se povećava linearno sa porastom veličine ulaza. Na primer, procedura koja sabira sve članove niza zahteva vreme proporcionalno dužini niza. Ovakav opis je pomalo netačan, jer vreme izvršavanja može znatno da odstupa od tačne proporcionalnosti, posebno za male vrednosti n. Za više informacija, pogledati članak notacija velikog O.
Linearno vreme se često smatra poželjnom osobinom algoritma. Ulažu se veliki napori u dizajn algoritama čije vreme izvršavanja je blisko linearnom vremenu ili kraće. U ova istraživanja ulaze i softverski i hardverski metodi. U slučaju hardverskih metoda, neki algoritmi, koji matematički uzev, nikad ne mogu da postignu linearno vreme sa standardnim modelom izračunavanja, se izvršavaju u linearnom vremenu. Postoje razne hardverske tehnologije koje koriste paralelizam da omoguće ovo.