---
title: Time complexity
slug: time-complexity
qid: 
snapshot: enwiki-001375818064
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1375818064
tags: [10639794, 111053174, 20129606, 22897028, 22964558, 23603337, 26220375, 29176158, 29176240]
---

# Time complexity

> [!note] Provenance
> Snapshot `enwiki-001375818064` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1375818064> · Licensed CC BY-SA 4.0

, showing the number of operations N as the result of input size n for each function 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.…

, showing the number of operations N as the result of input size n for each function 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, typically O(n) , O(n\log n) , O(n^\alpha) , O(2^n) , etc., where n is the size in units of bits needed to represent the input. Algorithmic complexities are classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity O(n) is a linear time algorithm and an algorithm with time complexity O(n^\alpha) for some constant \alpha > 0 is a polynomial time algorithm. The following table summarizes some classes of commonly encountered time complexities. In the table, \text{poly}(x) = x^{O(1)} , i.e., polynomial in x . An algorithm is termed constant time (often represented as O(1) time) when its complexity function T(n) 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, resulting in linear time complexity, or O(n) . However, if the number of elements is known and fixed, certain tasks can still be considered constant time. Importantly, the term "constant time" does not mean the running time must be entirely independent of the problem size; rather, it should have a consistent upper bound irrespective of input size. For example, a task that involves swapping the values of a and b to ensure a \le b is classified as constant time, even if the execution time may vary depending on whether the condition is already met. The key is that there exists a constant t such that the time taken will never exceed t , 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. 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 in alphabetical order. We suppose that, for 1 \le k \le n , one may access the k -th entry of the dictionary in a constant time. Let D(k) denote this k -th entry. Under these hypotheses, the test to see if a word w is in the dictionary may be done in logarithmic time: consider D\left(\left\lfloor \frac{n}{2} \right\rfloor\right) , where \lfloor\;\rfloor denotes the floor function. If w = D\left(\left\lfloor \frac{n}{2} \right\rfloor\right) --that is to say, the word w is exactly in the middle of the dictionary--then we are done. Else, if w --i.e., if the word w 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. 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. 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: Parallel algorithms that have linear or greater total work (allowing them to read the entire input), but sub-linear depth. Algorithms that have guaranteed assumptions on the input structure. An important example are operations on data structures, e.g. binary search in a sorted array. Algorithms that search for local structure in the input, for example finding a local minimum in a 1-D array (can be solved in O(\log(n)) time using a variant of binary search). A closely related notion is that of Local Computation Algorithms (LCA) where the algorithm receives a large input and queries to local information about some valid large output. == Quasilinear time == An algorithm is said to run in quasilinear time (also referred to as log-linear time) if T(n)=O(n\log^kn) for some positive constant k ; linearithmic time is the case k=1 . Using soft O notation these algorithms are \tilde{O}(n) . Quasilinear time algorithms are also O(n^{1+\varepsilon }) for every constant \varepsilon >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^2n) 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) Schönhage–Strassen algorithm for multiplication, O(n\log n\log \log n) In many cases, the O(n\log n) running time is simply the result of performing a \Theta (\log n) operation n times (for the notation, see ). For example, binary tree sort creates a binary tree by inserting each element of the n -sized array one by one. Since the insert operation on a self-balancing binary search tree takes O(\log n) time, the entire algorithm takes O(n\log n) time. Comparison sorts require at least \Omega (n\log n) comparisons in the worst case because \log (n!)=\Theta (n\log n) , by Stirling's approximation. They also frequently arise from the recurrence relation T(n) = 2T\left(\frac{n}{2}\right)+O(n) . 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, that is, 1=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 An^2 operations for some constant A . Thus it runs in time 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 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. 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. The worst case running time of a quasi-polynomial time algorithm is 2^{O(\log^c n)} for some fixed c > 0 . When c=1 this gives polynomial time, and for c 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, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of O(\log^3 n) ( n 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. \mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME} \left(2^{\log^c n}\right) ===First definition=== 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 \epsilon > 0 there exists an algorithm which solves the problem in time O(2^{n^\epsilon}) . The set of all such problems is the complexity class SUBEXP which can be defined in terms of DTIME as follows. \textsf{SUBEXP}=\bigcap_{\varepsilon>0} \textsf{DTIME}\left(2^{n^\varepsilon}\right) This notion of sub-exponential is non-uniform in terms of \epsilon in the sense that \epsilon is not part of the input and each ε may have its own algorithm for the problem. \textsf{SUBEPT}=\textsf{DTIME}\left(2^{o(k)} \cdot \text{poly}(n)\right). More precisely, SUBEPT is the class of all parameterized problems (L,k) for which there is a computable function f : \N \to \N with f \in o(k) and an algorithm that decides L in time 2^{f(k)} \cdot \text{poly}(n) . \textsf{EXP} = \bigcup_{c \in \mathbb{R_+}} \textsf{DTIME}\left(2^{n^c}\right) Sometimes, exponential time is used to refer to algorithms that have T(n) = 2^{O(n)} , where the exponent is at most a linear function of n . This gives rise to the complexity class E. \textsf{E} = \bigcup_{c \in \mathbb{N}} \textsf{DTIME}\left(2^{cn}\right) An algorithm is said to be factorial time if T(n) is upper bounded by the factorial function n! . Factorial time is a subset of exponential time (EXP) because n! \leq n^n = 2^{n \log n}= O \left(2^{n^{1 + \epsilon}} \right) for all \epsilon > 0 . 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. 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. \textsf{2-EXPTIME} = \bigcup_{c \in \N} \textsf{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.
