Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 

Time complexity

Index Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm. [1]

136 relations: Abstract machine, Ackermann function, Adleman–Pomerance–Rumely primality test, AKS primality test, Alexander Schrijver, Algorithm, Alphabetical order, Amortized analysis, Approximation algorithm, Array data structure, Asymptotic analysis, Average-case complexity, Big O notation, Binary number, Binary search algorithm, Binary tree, Bit, Boolean satisfiability problem, Boyer–Moore string-search algorithm, BPP (complexity), BQP, Brute-force search, Bubble sort, Clique problem, Cobham's thesis, Comparison sort, Complexity class, Computable function, Computational complexity, Computational complexity theory, Computational hardness assumption, Computer science, Conjunctive normal form, Content-addressable memory, Convolution theorem, Decision problem, Dictionary, Disjoint-set data structure, DLOGTIME, Double exponential function, DSPACE, DTIME, Dynamic programming, E (complexity), Element (mathematics), Elsevier, Euclidean algorithm, Exponential time hypothesis, Exponentiation by squaring, EXPTIME, ..., Fast Fourier transform, Floor and ceiling functions, Formal language, Function (mathematics), Game theory, General number field sieve, Graph (discrete mathematics), Graph coloring, Graph isomorphism problem, Gröbner basis, Greatest common divisor, Grover's algorithm, Heapsort, Infra-exponential, Insertion sort, Instruction set architecture, Integer factorization, Introsort, Iterated logarithm, Journal of Computer and System Sciences, K-d tree, Karmarkar's algorithm, L-notation, László Lovász, Lecture Notes in Computer Science, Linear programming, Logarithm, Machine learning, Matching (graph theory), Mathematical optimization, Matrix chain multiplication, Maximum subarray problem, Merge sort, Monge array, Non-deterministic Turing machine, NP (complexity), NP-completeness, NP-hardness, P (complexity), P versus NP problem, Parallel algorithm, Parallel computing, Parallel random-access machine, Parameterized complexity, Partial correlation, Patience sorting, Planted clique, Polygon triangulation, Polylogarithmic function, Polynomial, Presburger arithmetic, Priority queue, Probabilistic Turing machine, Property testing, Pseudo-polynomial time, Quantifier elimination, Quantum algorithm, Quantum Turing machine, Quicksort, Raimund Seidel, Random graph, Randomized algorithm, Real closed field, Recurrence relation, Reduction (complexity), Robustness (computer science), RP (complexity), Selection sort, Self-balancing binary search tree, Set cover problem, Shellsort, Smoothsort, Society for Industrial and Applied Mathematics, Sorting algorithm, Springer Science+Business Media, Steiner tree problem, Stirling's approximation, Time complexity, Travelling salesman problem, Tree sort, Turing machine, Ukkonen's algorithm, Upper and lower bounds, Worst-case complexity, ZPP (complexity), 2-EXPTIME. Expand index (86 more) »

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.

New!!: Time complexity and Abstract machine · See more »

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.

New!!: Time complexity and Ackermann function · See more »

Adleman–Pomerance–Rumely primality test

In computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime.

New!!: Time complexity and Adleman–Pomerance–Rumely primality test · See more »

AKS primality test

The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in a paper titled "PRIMES is in P".

New!!: Time complexity and AKS primality test · See more »

Alexander Schrijver

Alexander (Lex) Schrijver (born 4 May 1948 in Amsterdam) is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in Amsterdam.

New!!: Time complexity and Alexander Schrijver · See more »

Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Time complexity and Algorithm · See more »

Alphabetical order

Alphabetical order is a system whereby strings of characters are placed in order based on the position of the characters in the conventional ordering of an alphabet.

New!!: Time complexity and Alphabetical order · See more »

Amortized analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute.

New!!: Time complexity and Amortized analysis · See more »

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NP-hard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.

New!!: Time complexity and Approximation algorithm · See more »

Array data structure

In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

New!!: Time complexity and Array data structure · See more »

Asymptotic analysis

In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.

New!!: Time complexity and Asymptotic analysis · See more »

Average-case complexity

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.

New!!: Time complexity and Average-case complexity · See more »

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

New!!: Time complexity and Big O notation · See more »

Binary number

In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically 0 (zero) and 1 (one).

New!!: Time complexity and Binary number · See more »

Binary search algorithm

In computer science, binary search, also known as half-interval search,logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

New!!: Time complexity and Binary search algorithm · See more »

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the and the.

New!!: Time complexity and Binary tree · See more »

Bit

The bit (a portmanteau of binary digit) is a basic unit of information used in computing and digital communications.

New!!: Time complexity and Bit · See more »

Boolean satisfiability problem

In computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.

New!!: Time complexity and Boolean satisfiability problem · See more »

Boyer–Moore string-search algorithm

In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature.

New!!: Time complexity and Boyer–Moore string-search algorithm · See more »

BPP (complexity)

In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/2 for all instances.

New!!: Time complexity and BPP (complexity) · See more »

BQP

In computational complexity theory, BQP (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

New!!: Time complexity and BQP · See more »

Brute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

New!!: Time complexity and Brute-force search · See more »

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

New!!: Time complexity and Bubble sort · See more »

Clique problem

In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.

New!!: Time complexity and Clique problem · See more »

Cobham's thesis

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P (PTIME).

New!!: Time complexity and Cobham's thesis · See more »

Comparison sort

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.

New!!: Time complexity and Comparison sort · See more »

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

New!!: Time complexity and Complexity class · See more »

Computable function

Computable functions are the basic objects of study in computability theory.

New!!: Time complexity and Computable function · See more »

Computational complexity

In computer science, the computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.

New!!: Time complexity and Computational complexity · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Time complexity and Computational complexity theory · See more »

Computational hardness assumption

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where efficiently typically means "in polynomial time").

New!!: Time complexity and Computational hardness assumption · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Time complexity and Computer science · See more »

Conjunctive normal form

In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs.

New!!: Time complexity and Conjunctive normal form · See more »

Content-addressable memory

Content-addressable memory (CAM) is a special type of computer memory used in certain very-high-speed searching applications.

New!!: Time complexity and Content-addressable memory · See more »

Convolution theorem

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution is the pointwise product of Fourier transforms.

New!!: Time complexity and Convolution theorem · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: Time complexity and Decision problem · See more »

Dictionary

A dictionary, sometimes known as a wordbook, is a collection of words in one or more specific languages, often arranged alphabetically (or by radical and stroke for ideographic languages), which may include information on definitions, usage, etymologies, pronunciations, translation, etc.

New!!: Time complexity and Dictionary · See more »

Disjoint-set data structure

In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

New!!: Time complexity and Disjoint-set data structure · See more »

DLOGTIME

In computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine.

New!!: Time complexity and DLOGTIME · See more »

Double exponential function

A double exponential function is a constant raised to the power of an exponential function.

New!!: Time complexity and Double exponential function · See more »

DSPACE

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine.

New!!: Time complexity and DSPACE · See more »

DTIME

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine.

New!!: Time complexity and DTIME · See more »

Dynamic programming

Dynamic programming is both a mathematical optimization method and a computer programming method.

New!!: Time complexity and Dynamic programming · See more »

E (complexity)

In computational complexity theory, the complexity class E is the set of decision problems that can be solved by a deterministic Turing machine in time 2O(n) and is therefore equal to the complexity class DTIME(2O(n)).

New!!: Time complexity and E (complexity) · See more »

Element (mathematics)

In mathematics, an element, or member, of a set is any one of the distinct objects that make up that set.

New!!: Time complexity and Element (mathematics) · See more »

Elsevier

Elsevier is an information and analytics company and one of the world's major providers of scientific, technical, and medical information.

New!!: Time complexity and Elsevier · See more »

Euclidean algorithm

. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION.

New!!: Time complexity and Euclidean algorithm · See more »

Exponential time hypothesis

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by.

New!!: Time complexity and Exponential time hypothesis · See more »

Exponentiation by squaring

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix.

New!!: Time complexity and Exponentiation by squaring · See more »

EXPTIME

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that have exponential runtime, i.e., that are solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.

New!!: Time complexity and EXPTIME · See more »

Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components.

New!!: Time complexity and Fast Fourier transform · See more »

Floor and ceiling functions

In mathematics and computer science, the floor function is the function that takes as input a real number x and gives as output the greatest integer less than or equal to x, denoted \operatorname(x).

New!!: Time complexity and Floor and ceiling functions · See more »

Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

New!!: Time complexity and Formal language · See more »

Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

New!!: Time complexity and Function (mathematics) · See more »

Game theory

Game theory is "the study of mathematical models of conflict and cooperation between intelligent rational decision-makers".

New!!: Time complexity and Game theory · See more »

General number field sieve

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than.

New!!: Time complexity and General number field sieve · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: Time complexity and Graph (discrete mathematics) · See more »

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

New!!: Time complexity and Graph coloring · See more »

Graph isomorphism problem

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

New!!: Time complexity and Graph isomorphism problem · See more »

Gröbner basis

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field.

New!!: Time complexity and Gröbner basis · See more »

Greatest common divisor

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

New!!: Time complexity and Greatest common divisor · See more »

Grover's algorithm

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just O(\sqrt) evaluations of the function, where N is the size of the function's domain.

New!!: Time complexity and Grover's algorithm · See more »

Heapsort

In computer science, heapsort is a comparison-based sorting algorithm.

New!!: Time complexity and Heapsort · See more »

Infra-exponential

A growth rate is said to be infra-exponential or subexponential if it is dominated by all exponential growth rates, however great the doubling time.

New!!: Time complexity and Infra-exponential · See more »

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

New!!: Time complexity and Insertion sort · See more »

Instruction set architecture

An instruction set architecture (ISA) is an abstract model of a computer.

New!!: Time complexity and Instruction set architecture · See more »

Integer factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.

New!!: Time complexity and Integer factorization · See more »

Introsort

Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance.

New!!: Time complexity and Introsort · See more »

Iterated logarithm

In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

New!!: Time complexity and Iterated logarithm · See more »

Journal of Computer and System Sciences

The Journal of Computer and System Sciences (JCSS) is a peer-reviewed scientific journal in the field of computer science.

New!!: Time complexity and Journal of Computer and System Sciences · See more »

K-d tree

In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space.

New!!: Time complexity and K-d tree · See more »

Karmarkar's algorithm

Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems.

New!!: Time complexity and Karmarkar's algorithm · See more »

L-notation

L-notation is an asymptotic notation analogous to big-O notation, denoted as L_n for a bound variable n tending to infinity.

New!!: Time complexity and L-notation · See more »

László Lovász

László Lovász (born March 9, 1948) is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010.

New!!: Time complexity and László Lovász · See more »

Lecture Notes in Computer Science

Springer Lecture Notes in Computer Science (LNCS) is a series of computer science books published by Springer Science+Business Media (formerly Springer-Verlag) since 1973.

New!!: Time complexity and Lecture Notes in Computer Science · See more »

Linear programming

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

New!!: Time complexity and Linear programming · See more »

Logarithm

In mathematics, the logarithm is the inverse function to exponentiation.

New!!: Time complexity and Logarithm · See more »

Machine learning

Machine learning is a subset of artificial intelligence in the field of computer science that often uses statistical techniques to give computers the ability to "learn" (i.e., progressively improve performance on a specific task) with data, without being explicitly programmed.

New!!: Time complexity and Machine learning · See more »

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.

New!!: Time complexity and Matching (graph theory) · See more »

Mathematical optimization

In mathematics, computer science and operations research, mathematical optimization or mathematical programming, alternatively spelled optimisation, is the selection of a best element (with regard to some criterion) from some set of available alternatives.

New!!: Time complexity and Mathematical optimization · See more »

Matrix chain multiplication

Matrix chain multiplication (or Matrix Chain Ordering Problem, MCOP) is an optimization problem that can be solved using dynamic programming.

New!!: Time complexity and Matrix chain multiplication · See more »

Maximum subarray problem

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a, of numbers which has the largest sum, where, for 1 \leq i \leq j \leq n, M.

New!!: Time complexity and Maximum subarray problem · See more »

Merge sort

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm.

New!!: Time complexity and Merge sort · See more »

Monge array

In mathematics applied to computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge.

New!!: Time complexity and Monge array · See more »

Non-deterministic Turing machine

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers.

New!!: Time complexity and Non-deterministic Turing machine · See more »

NP (complexity)

In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.

New!!: Time complexity and NP (complexity) · See more »

NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Time complexity and NP-completeness · See more »

NP-hardness

NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".

New!!: Time complexity and NP-hardness · See more »

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.

New!!: Time complexity and P (complexity) · See more »

P versus NP problem

The P versus NP problem is a major unsolved problem in computer science.

New!!: Time complexity and P versus NP problem · See more »

Parallel algorithm

In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then combined together again at the end to get the correct result.

New!!: Time complexity and Parallel algorithm · See more »

Parallel computing

Parallel computing is a type of computation in which many calculations or the execution of processes are carried out concurrently.

New!!: Time complexity and Parallel computing · See more »

Parallel random-access machine

In computer science, a parallel random-access machine (PRAM) is a shared-memory abstract machine.

New!!: Time complexity and Parallel random-access machine · See more »

Parameterized complexity

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output.

New!!: Time complexity and Parameterized complexity · See more »

Partial correlation

In probability theory and statistics, partial correlation measures the degree of association between two random variables, with the effect of a set of controlling random variables removed.

New!!: Time complexity and Partial correlation · See more »

Patience sorting

In computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience.

New!!: Time complexity and Patience sorting · See more »

Planted clique

In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset.

New!!: Time complexity and Planted clique · See more »

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles, Chapter 3: Polygon Triangulation: pp.45–61.

New!!: Time complexity and Polygon triangulation · See more »

Polylogarithmic function

A polylogarithmic function in n is a polynomial in the logarithm of n, In computer science, polylogarithmic functions occur as the order of time or memory used by some algorithms (e.g., "it has polylogarithmic order").

New!!: Time complexity and Polylogarithmic function · See more »

Polynomial

In mathematics, a polynomial is an expression consisting of variables (also called indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables.

New!!: Time complexity and Polynomial · See more »

Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929.

New!!: Time complexity and Presburger arithmetic · See more »

Priority queue

In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.

New!!: Time complexity and Priority queue · See more »

Probabilistic Turing machine

In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which chooses between the available transitions at each point according to some probability distribution.

New!!: Time complexity and Probabilistic Turing machine · See more »

Property testing

In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem.

New!!: Time complexity and Property testing · See more »

Pseudo-polynomial time

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input) — but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

New!!: Time complexity and Pseudo-polynomial time · See more »

Quantifier elimination

Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science.

New!!: Time complexity and Quantifier elimination · See more »

Quantum algorithm

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation.

New!!: Time complexity and Quantum algorithm · See more »

Quantum Turing machine

A quantum Turing machine (QTM), also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer.

New!!: Time complexity and Quantum Turing machine · See more »

Quicksort

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

New!!: Time complexity and Quicksort · See more »

Raimund Seidel

Raimund G. Seidel is a German and Austrian theoretical computer scientist and an expert in computational geometry.

New!!: Time complexity and Raimund Seidel · See more »

Random graph

In mathematics, random graph is the general term to refer to probability distributions over graphs.

New!!: Time complexity and Random graph · See more »

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

New!!: Time complexity and Randomized algorithm · See more »

Real closed field

In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers.

New!!: Time complexity and Real closed field · See more »

Recurrence relation

In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

New!!: Time complexity and Recurrence relation · See more »

Reduction (complexity)

In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem.

New!!: Time complexity and Reduction (complexity) · See more »

Robustness (computer science)

In computer science, robustness is the ability of a computer system to cope with errors during execution1990.

New!!: Time complexity and Robustness (computer science) · See more »

RP (complexity)

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

New!!: Time complexity and RP (complexity) · See more »

Selection sort

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort.

New!!: Time complexity and Selection sort · See more »

Self-balancing binary search tree

In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.

New!!: Time complexity and Self-balancing binary search tree · See more »

Set cover problem

The set cover problem is a classical question in combinatorics, computer science and complexity theory.

New!!: Time complexity and Set cover problem · See more »

Shellsort

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort.

New!!: Time complexity and Shellsort · See more »

Smoothsort

In computer science, smoothsort is a comparison-based sorting algorithm.

New!!: Time complexity and Smoothsort · See more »

Society for Industrial and Applied Mathematics

The Society for Industrial and Applied Mathematics (SIAM) is an academic association dedicated to the use of mathematics in industry.

New!!: Time complexity and Society for Industrial and Applied Mathematics · See more »

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order.

New!!: Time complexity and Sorting algorithm · See more »

Springer Science+Business Media

Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.

New!!: Time complexity and Springer Science+Business Media · See more »

Steiner tree problem

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization.

New!!: Time complexity and Steiner tree problem · See more »

Stirling's approximation

In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials.

New!!: Time complexity and Stirling's approximation · See more »

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

New!!: Time complexity and Time complexity · See more »

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

New!!: Time complexity and Travelling salesman problem · See more »

Tree sort

A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.

New!!: Time complexity and Tree sort · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: Time complexity and Turing machine · See more »

Ukkonen's algorithm

In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995.

New!!: Time complexity and Ukkonen's algorithm · See more »

Upper and lower bounds

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set (K, ≤) is an element of K which is greater than or equal to every element of S. The term lower bound is defined dually as an element of K which is less than or equal to every element of S. A set with an upper bound is said to be bounded from above by that bound, a set with a lower bound is said to be bounded from below by that bound.

New!!: Time complexity and Upper and lower bounds · See more »

Worst-case complexity

In computer science, the worst-case complexity (usually denoted in asymptotic notation) measures the resources (e.g. running time, memory) an algorithm requires in the worst-case.

New!!: Time complexity and Worst-case complexity · See more »

ZPP (complexity)

In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

New!!: Time complexity and ZPP (complexity) · See more »

2-EXPTIME

In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know 2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an alternating Turing machine in exponential space.

New!!: Time complexity and 2-EXPTIME · See more »

Redirects here:

Algorithmic time complexity, Computation time, Computational time, Constant time, Cubic time, Double exponential time, Exponential algorithm, Exponential time, Fast algorithms, Linear time, Linear time agorithm, Linear-time, Linear-time algorithm, Linearithm, Linearithmic, Linearithmic function, Linearithmic time, Logarithmic time, N log n, Nlogn, Polylogarithmic time, Polynomial complexity, Polynomial time, Polynomial time algorithm, Polynomial-time, Polynomial-time algorithm, Polynomial-time solution, Polynomial-time solutions, Quadratic time, Quasi-polynomial time, Quasilinear time, Run-time complexity, Running time, SUBEXP, Strongly polynomial, Strongly polynomial time, Sub-exponential time, Sub-linear time, Subexponential time, Sublinear time, Sublinear time algorithm, Sublinear-time, Subquadratic time, Super-polynomial time, Superpolynomial, Weakly polynomial.

References

[1] https://en.wikipedia.org/wiki/Time_complexity

OutgoingIncoming
Hey! We are on Facebook now! »