blog-harianvirgo

The following table summarizes some classes of commonly encountered time complexities. In the table, poly( x ) =  x O (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( n 2) Binary search polylogarithmic time poly(log  n ) (log  n )2 fractional power O ( n c) where 0 < c < 1 n 1/2, n 2/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" ti...

An algorithm is said to be constant time (also written as O(1) time) if the value of T ( n ) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time. Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be bounded independently of the problem size. For example,...

An algorithm is said to take logarithmic time when T ( n ) = O(log n ) . Since log a n and log b n are related by a constant multiplier, and such a multiplier is irrelevant to big-O classification, the standard usage for logarithmic-time algorithms is O(log n ) regardless of the base of the logarithm appearing in the expression of T . Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search. An O(log n) algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size n is of the order of n . An example of logarithmic time is given by dictionary search. Consider a dictionary D which contains n entries, sorted by alphabetical order. We suppose that, for 1 ≤ k ≤ n , one may access the k th entry of the dic...

An algorithm is said to run in polylogarithmic time if its time T ( n ) is O ((log n ) k ) for some constant k . Another way to write this is O (log k n ) . For example, matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine, and a graph can be determined to be planar in a fully dynamic way in O(log3 n) time per insert/delete operation.

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...

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...

An algorithm is said to run in quasilinear time (also referred to as log-linear time ) if T ( n ) = O( n log k n ) for some positive constant k ; linearithmic time is the case k  = 1. Using soft O notation these algorithms are Õ( n ). Quasilinear time algorithms are also O( n 1+ε) for every constant ε > 0, and thus run faster than any polynomial time algorithm whose time bound includes a term n c for any c  > 1. Algorithms which run in quasilinear time include: In-place merge sort, O( n log 2 n ) Quicksort, O( n log n ), in its randomized version, has a running time that is O( n log n ) in expectation on the worst-case input. Its non-randomized version has an O( n log n ) running time only when considering average case complexity. Heapsort, O( n log n ), merge sort, introsort, binary tree sort, smoothsort, patience sorting, etc. in the worst case Fast Fourier transforms, O( n log n ) Monge array calculation, O( n log n ) In many cases, the n · log n running ti...

An algorithm is said to be subquadratic time if T ( n ) = o( n 2). For example, simple, comparison-based sorting algorithms are quadratic (e.g. insertion sort), but more advanced algorithms can be found that are subquadratic (e.g. shell sort). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T ( n ) = O( n k ) for some positive constant k . Problems for which a deterministic polynomial time algorithm exists belong to the complexity class P , which is central in the field of computational complexity theory. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast". Some examples of polynomial time algorithms: The selection sort sorting algorithm on n integers performs A n 2 {\displaystyle An^{2}} operations for some constant A . Thus it runs in time O ( n 2 ) {\displaystyle O(n^{2})} and is a polynomial time algorithm. All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time. Maximum matchings in graphs can be fou...

An algorithm is said to take superpolynomial time if T ( n ) is not bounded above by any polynomial. Using little omega notation, it is ω( n c ) time for all constants c , where n is the input parameter, typically the number of bits in the input. For example, an algorithm that runs for 2 n steps on an input of size n requires superpolynomial time (more specifically, exponential time). An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the Adleman–Pomerance–Rumely primality test runs for n O(log log n ) time on n -bit inputs; this grows faster than any polynomial for large enough n , but the input size must become impractically large before it cannot be dominated by a polynomial with small degree. An algorithm that requires superpolynomial time lies outside the complexity class P . Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since the P versu...

Quasi-polynomial time algorithms are algorithms that run longer than polynomial time, yet not so long as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is 2 O ( ( log ⁡ n ) c ) {\displaystyle 2^{O((\log n)^{c})}} for some fixed c > 0 {\displaystyle c>0} . For c = 1 {\displaystyle c=1} we get a polynomial time algorithm, for c < 1 {\displaystyle c<1} we get a sub-linear time algorithm. Quasi-polynomial time algorithms typically arise in reductions from an NP-hard problem to another problem. For example, one can take an instance of an NP hard problem, say 3SAT, and convert it to an instance of another problem B, but the size of the instance becomes 2 O ( ( log ⁡ n ) c ) {\displaystyle 2^{O((\log n)^{c})}} . In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B u...

The term sub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon, and we list the two most widely used ones below. First definition edit A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every ε > 0 there exists an algorithm which solves the problem in time O(2nε). The set of all such problems is the complexity class SUBEXP which can be defined in terms of DTIME as follows. SUBEXP = ⋂ ε > 0 DTIME ( 2 n ε ) {\displaystyle {\text{SUBEXP}}=\bigcap _{\va...

An algorithm is said to be exponential time , if T ( n ) is upper bounded by 2poly( n ), where poly( n ) is some polynomial in n . More formally, an algorithm is exponential time if T ( n ) is bounded by O(2 n k ) for some constant k . Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as EXP . EXP = ⋃ c ∈ N DTIME ( 2 n c ) {\displaystyle {\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)} Sometimes, exponential time is used to refer to algorithms that have T ( n ) = 2O( n ), where the exponent is at most a linear function of n . This gives rise to the complexity class E . E = ⋃ c ∈ N DTIME ( 2 c n ) {\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)}

An example of an algorithm that runs in factorial time is bogosort, a notoriously inefficient sorting algorithm based on trial and error. Bogosort sorts a list of n items by repeatedly shuffling the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the n ! orderings of the n items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the infinite monkey theorem.

An algorithm is said to be double exponential time if T ( n ) is upper bounded by 22poly( n ), where poly( n ) is some polynomial in n . Such algorithms belong to the complexity class 2-EXPTIME. 2-EXPTIME = ⋃ c ∈ N DTIME ( 2 2 n c ) {\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)} Well-known double exponential time algorithms include: Decision procedures for Presburger arithmetic Computing a Gröbner basis (in the worst case) Quantifier elimination on real closed fields takes at least double exponential time, and can be done in this time.