Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Big O notation
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Orders of common functions == {{Further|Time complexity#Table of common time complexities}} {{redirect|O(1)|the quasicoherent sheaf|Proj construction#The twisting sheaf of Serre}} Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, ''c'' is a positive constant and ''n'' increases without bound. The slower-growing functions are generally listed first. {| class="wikitable" |- !Notation !! Name !! Example |- |<math>O(1)</math> || [[Constant time|constant]] || Finding the median value for a sorted array of numbers; Calculating <math>(-1)^n</math>; Using a constant-size [[lookup table]] |- |<math>O(\alpha (n))</math> || [[inverse Ackermann function]] || Amortized complexity per operation for the [[Disjoint-set data structure]] |- |<math>O(\log \log n)</math> || double logarithmic || Average number of comparisons spent finding an item using [[interpolation search]] in a sorted array of uniformly distributed values |- |<math>O(\log n)</math> || [[Logarithmic time|logarithmic]] || Finding an item in a sorted array with a [[Binary search algorithm|binary search]] or a balanced search [[Tree data structure|tree]] as well as all operations in a [[binomial heap]] |- |<math>O((\log n)^c)</math><br /><math display=inline> c>1</math> || [[Polylogarithmic time|polylogarithmic]] || Matrix chain ordering can be solved in polylogarithmic time on a [[parallel random-access machine]]. |- |<math>O(n^c)</math><br /><math display=inline> 0<c<1</math> || fractional power || Searching in a [[k-d tree]] |- |<math>O(n)</math> || [[linear time|linear]] || Finding an item in an unsorted list or in an unsorted array; adding two ''n''-bit integers by [[Ripple carry adder|ripple carry]] |- |<math>O(n\log^* n)</math> || ''n'' [[log-star]] ''n'' || Performing [[Polygon triangulation|triangulation]] of a simple polygon using Seidel's algorithm,<ref>{{Citation |last=Seidel |first=Raimund |title=A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons |journal=[[Computational Geometry (journal)|Computational Geometry]] |volume=1 |pages=51β64 |year=1991 |citeseerx=10.1.1.55.5877 |doi=10.1016/0925-7721(91)90012-4 |author-link=Raimund Seidel |doi-access=free}}</ref> where <math>\log^*(n) = \begin{cases} 0, & \text{if }n \leq 1 \\ 1 + \log^*(\log n), & \text{if }n>1 \end{cases}</math> |- |<math>O(n\log n) = O(\log n!)</math> || [[Linearithmic time|linearithmic]], loglinear, quasilinear, or "''n'' log ''n''" || Performing a [[fast Fourier transform]]; fastest possible [[comparison sort]]; [[heapsort]] and [[merge sort]] |- |<math>O(n^2)</math> || [[quadratic time|quadratic]] || Multiplying two ''n''-digit numbers by [[Multiplication algorithm#Long multiplication|schoolbook multiplication]]; simple sorting algorithms, such as [[bubble sort]], [[selection sort]] and [[insertion sort]]; (worst-case) bound on some usually faster sorting algorithms such as [[quicksort]], [[Shellsort]], and [[tree sort]] |- |<math>O(n^c)</math> || [[polynomial time|polynomial]] or algebraic || [[Tree-adjoining grammar]] parsing; maximum [[Matching (graph theory)|matching]] for [[bipartite graph]]s; finding the [[determinant]] with [[LU decomposition]] |- |<math>L_n[\alpha,c] = e^{(c + o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}</math><br /><math display=inline> 0 < \alpha < 1</math> || [[L-notation]] or [[sub-exponential time|sub-exponential]] || Factoring a number using the [[quadratic sieve]] or [[General number field sieve|number field sieve]] |- |<math>O(c^n)</math><br/><math display=inline> c>1</math> || [[exponential time|exponential]] || Finding the (exact) solution to the [[travelling salesman problem]] using [[dynamic programming]]; determining if two logical statements are equivalent using [[brute-force search]] |- |<math>O(n!)</math> || [[factorial]] || Solving the [[travelling salesman problem]] via brute-force search; generating all unrestricted permutations of a [[Partially ordered set|poset]]; finding the [[determinant]] with [[Laplace expansion]]; enumerating [[Bell number|all partitions of a set]] |} The statement <math>f(n) = O(n!)</math> is sometimes weakened to <math>f(n) = O\left(n^n\right)</math> to derive simpler formulas for asymptotic complexity. For any <math>k>0</math> and {{nowrap|<math>c > 0</math>,}} <math>O(n^c(\log n)^k)</math> is a subset of <math>O(n^{c+\varepsilon})</math> for any {{nowrap|<math> \varepsilon > 0</math>,}} so may be considered as a polynomial with some bigger order.
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)