1

constant

𝛼(𝑛)

inverse Ackermann

𝑙𝑜𝑔*(𝑛) ≈ 𝑠𝑙𝑜𝑔(𝑛)

iterated/super logarithmic

𝑙𝑜𝑔(𝑙𝑜𝑔(𝑛))

log-logarithmic

𝑙𝑜𝑔(𝑛)

logarithmic

𝑙𝑜𝑔(𝑛)^𝑘 where 𝑘 > 1

poly-logarithmic

𝑛^𝑘 where 0 < 𝑘 < 1

fractional power

𝑛

linear

𝑛 𝑙𝑜𝑔*(𝑛)

n log-star n

𝑛 𝑙𝑜𝑔(𝑛) ≈ 𝑙𝑜𝑔(𝑛!)

linearithmic

𝑛 𝑙𝑜𝑔(𝑛)^𝑘where 𝑘 > 1

quasi-linear

𝑛^𝑘 where 𝑘 > 1

𝑘^{𝑙𝑜𝑔(𝑛)}where 𝑘 > 1

polynomial

• sub-polynomial = anything above
• super-polynomial = anything below
• quadratic = 𝑛²
• cubic = 𝑛³

𝑘^{𝑙𝑜𝑔(𝑛)𝑐} where 𝑐 > 1 and 𝑘 > 1

quasi-polynomial or pseudo-polynomial

𝑂(2^𝑛𝑒) for all 𝑒 > 0

sub-exponential (1^st definition)

2^𝑜(𝑛)

sub-exponential (2^nd definition)

𝑘^𝑛 where 𝑘 > 1

exponential

𝑛!

factorial

𝑛^𝑛

super exponential

𝑐^{(𝑘𝑝𝑜𝑙𝑦(𝑛))}

double exponential time