| Complexity | Name | Examples, Comments |
|---|---|---|
| Θ(1) | Constant | Hash table lookup and modification |
| Θ(lg n) | Logarithmic | Binary search. Logarithm base unimportant. |
| Θ(n) | Linear | Iterating over a list. |
| Θ(n lg n) | Loglinear | Optimal sorting of arbitrary values. Same as Θ(lg n!). |
| Θ(n2) | Quadratic | Comparing n objects to each other |
| Θ(n3) | Cubic | Floyd and Warshall's algorithms |
| O(nk) | Polynomial | k nested for loops over n (if k is a positive integer). For any constant k > 0. |
| Ω(kn) | Exponential | Producing every subset of n items (k = 2). Any k > 1. |
| Θ(n!) | Factorial | Producing every ordering of n values. |
Hetland, Magnus Lie. "Chapter 2 - The Basics". Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition. Apress. © 2014. Books24x7. <http://common.books24x7.com.ezproxy.rit.edu/toc.aspx?bookid=72529> (accessed February 6, 2015)