Table of common time complexities




The following table summarizes some classes of commonly encountered time complexities. In the table, poly(x) = xO(1), i.e., polynomial in x.

Name Complexity class Running time (T(n)) Examples of running times Example algorithms
constant time O(1) 10 Finding the median value in a sorted array of numbers

Calculating (−1)n

inverse Ackermann time O(α(n)) Amortized time per operation using a disjoint set
iterated logarithmic time O(log* n) Distributed coloring of cycles
log-logarithmic O(log log n) Amortized time per operation using a bounded priority queue
logarithmic time DLOGTIME O(log n) log n, log(n2) Binary search
polylogarithmic time poly(log n) (log n)2
fractional power O(nc) where 0 < c < 1 n1/2, n2/3 Searching in a kd-tree
linear time O(n) n, 2n + 5 Finding the smallest or largest item in an unsorted array, Kadane's algorithm, linear search
"n log-star n" time O(n log* n) Seidel's polygon triangulation algorithm.
linearithmic time O(n log n) n log n, log n! Fastest possible comparison sort; Fast Fourier transform.
quasilinear time n poly(log n)
quadratic time O(n2) n2 Bubble sort; Insertion sort; Direct convolution
cubic time O(n3) n3 Naive multiplication of two n×n matrices. Calculating partial correlation.
polynomial time P 2O(log n) = poly(n) n2 + n, n10 Karmarkar's algorithm for linear programming; AKS primality test
quasi-polynomial time QP 2poly(log n) nlog log n, nlog n Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem.
sub-exponential time
(first definition)		 SUBEXP O(2nε) for all ε > 0 Contains BPP unless EXPTIME (see below) equals MA.
sub-exponential time
(second definition)		 2o(n) 2n1/3 Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism
exponential time
(with linear exponent)		 E 2O(n) 1.1n, 10n Solving the traveling salesman problem using dynamic programming
exponential time EXPTIME 2poly(n) 2n, 2n2 Solving matrix chain multiplication via brute-force search
factorial time O(n!) n! Solving the traveling salesman problem via brute-force search
double exponential time 2-EXPTIME 22poly(n) 22n Deciding the truth of a given statement in Presburger arithmetic

Comments

Post a Comment

Popular posts from this blog

43)Sheikh Hasina the right choice as main guest to the Republic Day but trust the PMO to miss the obvious

India Republic Day -- From your record 10 Chief Guests for the Republic Day Ornement in 2018 to none in 2021 is as considerably a reflection on Prime Minister Narendra Modis out of the box approach to foreign policy. From your record 10 Chief Guests for the Republic Day Ornement in 2018 to none in 2021 is as considerably a reflection on Prime Minister Narendra Modis out of the box approach to foreign policy as his blind spots whilst zeroing in on an extraordinary foreign dignitary. Sheikh Hasina Prime Minister of Bangladesh would have been the perfect Republic Day Chief Guest this current year for umpteen reasons nevertheless it obviously didnt occur to Modi to single her out there for the honour. I shiver to even speculate if the visionary and statesman similar to Modi is blinded through her religion or sexual category or both to pass your girlfriend up? Instead of inviting United kingdom PM Boris Johnson who have ultimately chickened out Hasina should have been Modis auto choic
Read more

Linear time

An algorithm is said to take linear time , or O ( n ) time, if its time complexity is O ( n ) . Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant c such that the running time is at most cn for every input of size n . For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant. Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory. This concept of linear time is used in string matching a
Read more

Sub-linear time

An algorithm is said to run in sub-linear time (often spelled sublinear time ) if T ( n ) = o( n ). In particular this includes algorithms with the time complexities defined above. Typical algorithms that are exact and yet run in sub-linear time use parallel processing (as the NC 1 matrix determinant calculation does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time binary search and many tree maintenance algorithms do). However, formal languages such as the set of all strings that have a 1-bit in the position indicated by the first log(n) bits of the string may depend on every bit of the input and yet be computable in sub-linear time. The specific term sublinear time algorithm is usually reserved to algorithms that are unlike the above in that they are run over classical serial machine models and are not allowed prior assumptions on the input. They are however allowed to be randomized, and indeed must be randomized for all but the most t
Read more