↑ arvau

Wikipedia / Time complexity

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed as a function of the size of the input. Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the asymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation is the size in units of bits needed to represent the input.

is a linear time algorithm is a polynomial time algorithm.

Table of common time complexities

.An algorithm is termed constant time is bounded by a value that does not change with the size of the input. This implies that the execution time remains consistent regardless of how much data is processed. For instance, accessing a specific element in an array is a constant-time operation, as it requires only a single operation to locate that element.

In contrast, determining the minimum value in an unordered array is not constant time; it requires examining each element. However, if the number of elements is known and fixed, certain tasks can still be considered constant time.

, regardless of the input values.

Constant-time algorithms are especially significant in contexts like cryptography, where timing attacks can exploit variations in execution time. By designing algorithms that run in constant time, developers can enhance security and ensure performance predictability, making it a fundamental consideration in software engineering.

Logarithmic time

An algorithm is said to take logarithmic time are related by a constant multiplier, and such a multiplier is irrelevant.

Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.

.

An example of logarithmic time is given by dictionary search. Consider a dictionary entries, sorted in alphabetical order denotes the floor function comes earlier in alphabetical order than the middle word of the whole dictionary--we continue the search in the same way in the left (i.e. earlier) half of the dictionary, and then again repeatedly until the correct word is found. Otherwise, if it comes after the middle word, continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary. As a result, the search space within the dictionary decreases as the algorithm gets closer to the target word.

Polylogarithmic time

An algorithm is said to run in polylogarithmic time.

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 time per insert/delete operation.

Sub-linear time

An algorithm is said to run in sub-linear time (often spelled sublinear time. In particular this includes algorithms with the time complexities defined above.

The specific term sublinear time algorithm commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently to approximately infer properties of the entire instance. This type of sublinear time algorithm is closely related to property testing and statistics.

Other settings where algorithms can run in sublinear time include:

Linear time

An algorithm is said to take linear time. 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 algorithms such as the Boyer–Moore string-search algorithm and Ukkonen's algorithm.

Quasilinear time

An algorithm is said to run in quasilinear time (also referred to as log-linear time; linearithmic time. Using soft O notation.

Algorithms which run in quasilinear time include:

times (for the notation, see ). For example, binary tree sort creates a binary tree-sized array one by one. Since the insert operation on a self-balancing binary search tree time.

Comparison sorts, by Stirling's approximation. They also frequently arise from the recurrence relation.

Sub-quadratic time

An algorithm is said to be subquadratic time.

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.

Polynomial time

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial. 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 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 found in polynomial time. In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms.

These two concepts are only relevant if the inputs to the algorithms consist of integers.

Complexity classes

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

P is the smallest time-complexity class on a deterministic machine which is robust in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

Superpolynomial time

An algorithm is defined to take superpolynomial time.

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, 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 versus NP problem is unresolved, it is unknown whether NP-complete problems require superpolynomial time.

Quasi-polynomial time

Quasi-polynomial time algorithms are algorithms whose running time exhibits quasi-polynomial growth, a type of behavior that may be slower than polynomial time but yet is significantly faster than exponential time it gives sub-linear time.

There are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed Steiner tree problem being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.

Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the planted clique problem in which the goal is to find a large clique in the union of a clique and a random graph. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a computational hardness assumption to prove the difficulty of several other problems in computational game theory, property testing, and machine learning.

The complexity class QP consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of DTIME as follows.

Relation to NP-complete problems

In complexity theory, the unsolved P versus NP problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for NP-complete problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is the square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the exponential time hypothesis. Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of approximation algorithms make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the set cover problem.

Sub-exponential time

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, however the two most widely used are below.

First definition

. The set of all such problems is the complexity class SUBEXP which can be defined in terms of DTIME as follows.

is not part of the input and each ε may have its own algorithm for the problem.

Second definition

. This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the general number field sieve. Another example was the graph isomorphism problem. However, at STOC 2016 a quasi-polynomial time algorithm was presented.

It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In parameterized complexity of decision problems. SUBEPT:

for which there is a computable function.

Exponential time hypothesis

The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form. The exponential time hypothesis implies P ≠ NP.

Exponential time

An algorithm is said to be exponential time. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as EXP.

. This gives rise to the complexity class E.

Factorial time

An algorithm is said to be factorial time is upper bounded by the factorial function. However, it is not a subset of E.

An example of an algorithm that runs in factorial time is bogosort, a notoriously inefficient sorting algorithm based on trial and error items by repeatedly shuffling items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the infinite monkey theorem.

Double exponential time

An algorithm is said to be double exponential. Such algorithms belong to the complexity class 2-EXPTIME.

Well-known double exponential time algorithms include:

See also

References