Common asymptotic functions

Function

1

log n

n

n log n

n2

n3

2n

n!

Name

constant function

logarithmic

linear

---

quadratic

cubic

exponential

factorial

nk for any constant k:

polynomial function

f(n) is O(one of these functions) ==> f(n) is O(every lower[?]

function as well)

Previous slide

Back to first slide

View graphic version