Eksponencijalno vreme
U teoriji kompleksnosti, za neki problem se kaže da ima eksponencijalno vreme izračunavanja ako je za njegovo izračunavanje potrebno vreme m(n), koje je ograničeno eksponencijalnom funkcijom veličine problema, n. Drugim rečima, kada se veličina problema povećava linearno, vreme potrebno za rešavanje problema se povećava eksponencijalno.
Zapiano matematički, postoji k > 1 takvo da je m(n) = Θ(kn) i postoji c, takvo da je m(n) = O(cn).
Informatičari obično smatraju da su algoritmi koji zahtevaju polinomijalno vreme brzi, a da su svi algoritmi koji zahtevaju vreme duže od polinomijalnog spori (vidi Kobhamovu tezu). Po ovoj definiciji, eksponencijalno vreme bi se stoga smatralo sporim. Ovakva klasifikacija pruža korisnu predstavu, ali je neprecizna. U praksi, vreme koje je algoritmu zaista potrebno za izvršavanje zavisi od veličine ulaza, n, i od konstanti (vidi notacija velikog O za više detalja). Za dati ulaz n, neki polinomijalni algoritam može da ima veće vreme izvršavanja nego neki eksponencijalni algoritam. Međutim, za dovoljno velike vrednosti n, vreme izvršavanja eksponencijalnog algoritma će postati veće.
Postoje algoritmi koji zahtevaju više vremena od polinomijalnog vremena (super-polinomijalno vreme) ali manje od eksponencijalnog vremena (sub-eksponencijalno vreme). Jedan takav primer je najbolji poznati algoritam za faktorizaciju celih brojeva. Ovakvi algoritmi se takođe smatraju sporim.
Česta je greška da se kvadratno vreme smatra eksponencijalnim. Kvadratno vreme se odnosi na specijalni slučaj polinomijalnog vremena, kod koga je najveći eksponent jednak 2, na primer n2. Eksponencijalno vreme podrazumeva da promenljiva stoji u eksponentu, na primer 2n. Problemi za čije rešavanje je potrebno kvadratno ili polinomijalno vreme, mogu biti vremenski zahtevni, ali obično spadaju u probleme koji se u praksi mogu rešiti. (mada je i kvadratno vreme ponekad neprihvatljivo kada su u pitanju interaktivne aplikacije). Za probleme koji zahtevaju eksponencijalno vreme se smatra da u praksi nisu rešivi, izuzev za male ulazne vrednosti.