Faster access than browser!
97 relations: Abuse of notation, Acta Mathematica, Adder (electronics), Algorithm, Analysis of algorithms, Analytic number theory, Arithmetic function, Asymptotic analysis, Asymptotic expansion, Asymptotically optimal algorithm, Bell number, Big O in probability notation, Big O notation, Binary search algorithm, Binomial heap, Bipartite graph, Brute-force search, Bubble sort, Cambridge University Press, Charles E. Leiserson, Clifford Stein, Coefficient, Comparison sort, Complex analysis, Computational complexity theory, Computer science, Convex cone, Derivative, Determinant, Differentiable function, Donald Knuth, Dynamic programming, Edmund Landau, Equivalence relation, Factorial, Fast Fourier transform, Filter (mathematics), Function (mathematics), G. H. Hardy, General number field sieve, Heapsort, If and only if, Infinitesimal, Infinity, Insertion sort, Integer factorization, Integral transform, Interpolation search, Introduction to Algorithms, Iterated logarithm, ..., Ivan Vinogradov, John Edensor Littlewood, K-d tree, Kirkpatrick–Seidel algorithm, L-notation, Laplace expansion, LaTeX, Limit superior and limit inferior, Lookup table, LU decomposition, Matching (graph theory), Mathematics, Merge sort, Nachbin's theorem, Net (mathematics), Nicolaas Govert de Bruijn, Normed vector space, Notices of the American Mathematical Society, Omega, Omicron, Order of approximation, Parallel random-access machine, Partially ordered set, Paul Gustav Heinrich Bachmann, Polygon triangulation, Prime number theorem, Proof of O(log*n) time complexity of union–find, Quadratic sieve, Quicksort, Real number, Ron Rivest, Selection sort, Set notation, Shellsort, Symmetric relation, Taylor series, Term (logic), Thomas H. Cormen, Time complexity, Topological group, Travelling salesman problem, Tree (data structure), Tree sort, Tree-adjoining grammar, Uniform norm, Upper and lower bounds, 0. Expand index (47 more) »
Abuse of notation
In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not formally correct but that seems likely to simplify the exposition or suggest the correct intuition (while being unlikely to introduce errors or cause confusion).
New!!: Big O notation and Abuse of notation · See more »
Acta Mathematica
Acta Mathematica is a peer-reviewed open-access scientific journal covering research in all fields of mathematics.
New!!: Big O notation and Acta Mathematica · See more »
Adder (electronics)
An adder is a digital circuit that performs addition of numbers.
New!!: Big O notation and Adder (electronics) · See more »
Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
New!!: Big O notation and Algorithm · See more »
Analysis of algorithms
In computer science, the analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.
New!!: Big O notation and Analysis of algorithms · See more »
Analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers.
New!!: Big O notation and Analytic number theory · See more »
Arithmetic function
In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers.
New!!: Big O notation and Arithmetic function · See more »
Asymptotic analysis
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
New!!: Big O notation and Asymptotic analysis · See more »
Asymptotic expansion
In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular, often infinite, point.
New!!: Big O notation and Asymptotic expansion · See more »
Asymptotically optimal algorithm
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm.
New!!: Big O notation and Asymptotically optimal algorithm · See more »
Bell number
In combinatorial mathematics, the Bell numbers count the possible partitions of a set.
New!!: Big O notation and Bell number · See more »
Big O in probability notation
The order in probability notation is used in probability theory and statistical theory in direct parallel to the big-O notation that is standard in mathematics.
New!!: Big O notation and Big O in probability notation · 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!!: Big O notation and Big O notation · 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!!: Big O notation and Binary search algorithm · See more »
Binomial heap
In computer science, a binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps.
New!!: Big O notation and Binomial heap · See more »
Bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.
New!!: Big O notation and Bipartite graph · 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!!: Big O notation 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!!: Big O notation and Bubble sort · See more »
Cambridge University Press
Cambridge University Press (CUP) is the publishing business of the University of Cambridge.
New!!: Big O notation and Cambridge University Press · See more »
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof.
New!!: Big O notation and Charles E. Leiserson · See more »
Clifford Stein
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.
New!!: Big O notation and Clifford Stein · See more »
Coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series or any expression; it is usually a number, but may be any expression.
New!!: Big O notation and Coefficient · 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!!: Big O notation and Comparison sort · See more »
Complex analysis
Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers.
New!!: Big O notation and Complex analysis · 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!!: Big O notation and Computational complexity theory · 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!!: Big O notation and Computer science · See more »
Convex cone
In linear algebra, a convex cone is a subset of a vector space over an ordered field that is closed under linear combinations with positive coefficients.
New!!: Big O notation and Convex cone · See more »
Derivative
The derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value).
New!!: Big O notation and Derivative · See more »
Determinant
In linear algebra, the determinant is a value that can be computed from the elements of a square matrix.
New!!: Big O notation and Determinant · See more »
Differentiable function
In calculus (a branch of mathematics), a differentiable function of one real variable is a function whose derivative exists at each point in its domain.
New!!: Big O notation and Differentiable function · See more »
Donald Knuth
Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.
New!!: Big O notation and Donald Knuth · See more »
Dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method.
New!!: Big O notation and Dynamic programming · See more »
Edmund Landau
Edmund Georg Hermann Landau (14 February 1877 – 19 February 1938) was a German mathematician who worked in the fields of number theory and complex analysis.
New!!: Big O notation and Edmund Landau · See more »
Equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive.
New!!: Big O notation and Equivalence relation · See more »
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, The value of 0! is 1, according to the convention for an empty product.
New!!: Big O notation and Factorial · 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!!: Big O notation and Fast Fourier transform · See more »
Filter (mathematics)
In mathematics, a filter is a special subset of a partially ordered set.
New!!: Big O notation and Filter (mathematics) · See more »
Function (mathematics)
In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.
New!!: Big O notation and Function (mathematics) · See more »
G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis.
New!!: Big O notation and G. H. Hardy · 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!!: Big O notation and General number field sieve · See more »
Heapsort
In computer science, heapsort is a comparison-based sorting algorithm.
New!!: Big O notation and Heapsort · See more »
If and only if
In logic and related fields such as mathematics and philosophy, if and only if (shortened iff) is a biconditional logical connective between statements.
New!!: Big O notation and If and only if · See more »
Infinitesimal
In mathematics, infinitesimals are things so small that there is no way to measure them.
New!!: Big O notation and Infinitesimal · See more »
Infinity
Infinity (symbol) is a concept describing something without any bound or larger than any natural number.
New!!: Big O notation and Infinity · 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!!: Big O notation and Insertion sort · See more »
Integer factorization
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.
New!!: Big O notation and Integer factorization · See more »
Integral transform
In mathematics, an integral transform maps an equation from its original domain into another domain where it might be manipulated and solved much more easily than in the original domain.
New!!: Big O notation and Integral transform · See more »
Interpolation search
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).
New!!: Big O notation and Interpolation search · See more »
Introduction to Algorithms
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
New!!: Big O notation and Introduction to Algorithms · 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!!: Big O notation and Iterated logarithm · See more »
Ivan Vinogradov
Ivan Matveevich Vinogradov (a; 14 September 1891 – 20 March 1983) (not to be confused with Askold Ivanovich Vinogradov of the Bombieri-Vinogradov theorem) was a Soviet mathematician, who was one of the creators of modern analytic number theory, and also a dominant figure in mathematics in the USSR.
New!!: Big O notation and Ivan Vinogradov · See more »
John Edensor Littlewood
John Edensor Littlewood FRS LLD (9 June 1885 – 6 September 1977) was an English mathematician.
New!!: Big O notation and John Edensor Littlewood · 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!!: Big O notation and K-d tree · See more »
Kirkpatrick–Seidel algorithm
The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with \mathcal(n \log h) time complexity, where n is the number of input points and h is the number of points (non dominated or maximal points, as called in some texts) in the hull.
New!!: Big O notation and Kirkpatrick–Seidel 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!!: Big O notation and L-notation · See more »
Laplace expansion
In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression for the determinant |B| of an n × n matrix B that is a weighted sum of the determinants of n sub-matrices of B, each of size (n−1) × (n−1).
New!!: Big O notation and Laplace expansion · See more »
LaTeX
LaTeX (or; a shortening of Lamport TeX) is a document preparation system.
New!!: Big O notation and LaTeX · See more »
Limit superior and limit inferior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (i.e., eventual and extreme) bounds on the sequence.
New!!: Big O notation and Limit superior and limit inferior · See more »
Lookup table
In computer science, a lookup table is an array that replaces runtime computation with a simpler array indexing operation.
New!!: Big O notation and Lookup table · See more »
LU decomposition
In numerical analysis and linear algebra, LU decomposition (where "LU" stands for "lower–upper", and also called LU factorization) factors a matrix as the product of a lower triangular matrix and an upper triangular matrix.
New!!: Big O notation and LU decomposition · 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!!: Big O notation and Matching (graph theory) · See more »
Mathematics
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
New!!: Big O notation and Mathematics · See more »
Merge sort
In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm.
New!!: Big O notation and Merge sort · See more »
Nachbin's theorem
In mathematics, in the area of complex analysis, Nachbin's theorem (named after Leopoldo Nachbin) is commonly used to establish a bound on the growth rates for an analytic function.
New!!: Big O notation and Nachbin's theorem · See more »
Net (mathematics)
In mathematics, more specifically in general topology and related branches, a net or Moore–Smith sequence is a generalization of the notion of a sequence.
New!!: Big O notation and Net (mathematics) · See more »
Nicolaas Govert de Bruijn
Nicolaas Govert (Dick) de Bruijn (9 July 1918 – 17 February 2012) was a Dutch mathematician, noted for his many contributions in the fields of analysis, number theory, combinatorics and logic.
New!!: Big O notation and Nicolaas Govert de Bruijn · See more »
Normed vector space
In mathematics, a normed vector space is a vector space over the real or complex numbers, on which a norm is defined.
New!!: Big O notation and Normed vector space · See more »
Notices of the American Mathematical Society
Notices of the American Mathematical Society is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue.
New!!: Big O notation and Notices of the American Mathematical Society · See more »
Omega
Omega (capital: Ω, lowercase: ω; Greek ὦ, later ὦ μέγα, Modern Greek ωμέγα) is the 24th and last letter of the Greek alphabet.
New!!: Big O notation and Omega · See more »
Omicron
Omicron (uppercase Ο, lowercase ο, literally "small o": όμικρον back rounded vowel. Letters that arose from omicron include Roman O and Cyrillic O. The upper-case letter of omicron (O) was originally used in mathematics as a symbol for Big O notation (representing a function's asymptotic growth rate), but has fallen out of favor because omicron is indistinguishable from the Latin letter O and easily confused with the digit zero (0). Omicron is used to designate the fifteenth star in a constellation group, its ordinal placement a function of both magnitude and position. Such stars include Omicron Andromedae, Omicron Ceti, and Omicron Persei.
New!!: Big O notation and Omicron · See more »
Order of approximation
In science, engineering, and other quantitative disciplines, orders of approximation refer to formal or informal terms for how precise an approximation is, and to indicate progressively more refined approximations: in increasing order of precision, a zeroth-order approximation, a first-order approximation, a second-order approximation, and so forth.
New!!: Big O notation and Order of approximation · See more »
Parallel random-access machine
In computer science, a parallel random-access machine (PRAM) is a shared-memory abstract machine.
New!!: Big O notation and Parallel random-access machine · See more »
Partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set.
New!!: Big O notation and Partially ordered set · See more »
Paul Gustav Heinrich Bachmann
Paul Gustav Heinrich Bachmann (22 June 1837 – 31 March 1920) was a German mathematician.
New!!: Big O notation and Paul Gustav Heinrich Bachmann · 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!!: Big O notation and Polygon triangulation · See more »
Prime number theorem
In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers.
New!!: Big O notation and Prime number theorem · See more »
Proof of O(log*n) time complexity of union–find
In computer science, Union Find is an algorithm for doing certain operations on sets.
New!!: Big O notation and Proof of O(log*n) time complexity of union–find · See more »
Quadratic sieve
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve).
New!!: Big O notation and Quadratic sieve · 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!!: Big O notation and Quicksort · See more »
Real number
In mathematics, a real number is a value of a continuous quantity that can represent a distance along a line.
New!!: Big O notation and Real number · See more »
Ron Rivest
Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.
New!!: Big O notation and Ron Rivest · See more »
Selection sort
In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort.
New!!: Big O notation and Selection sort · See more »
Set notation
Sets are fundamental objects in mathematics.
New!!: Big O notation and Set notation · See more »
Shellsort
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort.
New!!: Big O notation and Shellsort · See more »
Symmetric relation
In mathematics and other areas, a binary relation R over a set X is symmetric if it holds for all a and b in X that a is related to b if and only if b is related to a. In mathematical notation, this is: Symmetry, along with reflexivity and transitivity, are the three defining properties of an equivalence relation.
New!!: Big O notation and Symmetric relation · See more »
Taylor series
In mathematics, a Taylor series is a representation of a function as an infinite sum of terms that are calculated from the values of the function's derivatives at a single point.
New!!: Big O notation and Taylor series · See more »
Term (logic)
In analogy to natural language, where a noun phrase refers to an object and a whole sentence refers to a fact, in mathematical logic, a term denotes a mathematical object and a formula denotes a mathematical fact.
New!!: Big O notation and Term (logic) · See more »
Thomas H. Cormen
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.
New!!: Big O notation and Thomas H. Cormen · 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!!: Big O notation and Time complexity · See more »
Topological group
In mathematics, a topological group is a group G together with a topology on G such that the group's binary operation and the group's inverse function are continuous functions with respect to the topology.
New!!: Big O notation and Topological group · 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!!: Big O notation and Travelling salesman problem · See more »
Tree (data structure)
In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
New!!: Big O notation and Tree (data structure) · 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!!: Big O notation and Tree sort · See more »
Tree-adjoining grammar
Tree-adjoining grammar (TAG) is a grammar formalism defined by Aravind Joshi.
New!!: Big O notation and Tree-adjoining grammar · See more »
Uniform norm
In mathematical analysis, the uniform norm (or sup norm) assigns to real- or complex-valued bounded functions f defined on a set S the non-negative number This norm is also called the supremum norm, the Chebyshev norm, or the infinity norm. The name "uniform norm" derives from the fact that a sequence of functions \ converges to f under the metric derived from the uniform norm if and only if f_n converges to f uniformly.
New!!: Big O notation and Uniform norm · 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!!: Big O notation and Upper and lower bounds · See more »
0
0 (zero) is both a number and the numerical digit used to represent that number in numerals.
New!!: Big O notation and 0 · See more »
Redirects here:
Asymptotic Growth of Functions, Asymptotic bound, Asymptotic estimate, Asymptotic growth of functions, Asymptotic lower bound, Asymptotic notation, Asymptotic run time, Asymptotic running time, Asymptotic upper bound, Asymptotically tight bound, Bachmann-Landau notation, Bachmann–Landau notation, Big O Notation, Big Oh, Big Oh notation, Big Theta, Big Theta notation, Big o notation, Big oh, Big oh notation, Big omega notation, Big omicron notation, Big theta, Big theta notation, Big-O Notation, Big-O notation, Big-Theta, Big-Theta Notation, Big-o notation, Big-oh, Big-omega notation, Big-theta notation, Bigonotation, Constant factor, Constant factors, Hardy notation, Landau gauge symbol, Landau notation, Landau symbol, Landau symbols, Landau's symbol, Little O, Little O notation, Little o, Little o notation, Little oh, Little-o, Little-o notation, O notation, O(), O(1), O(n!), O(nˆ2), O-notation, O-speedup, O-symbol, Onotation, Order notation, Order of, Order of a sequence, Properties of O and o, Small o notation, Soft O, Soft O notation, Theta notation.
References
[1] https://en.wikipedia.org/wiki/Big_O_notation
