Find link

language:

Find link is a tool written by Edward Betts.

searching for Worst-case complexity 69 found (93 total)

Median of medians (2,608 words) [view diff] exact match in snippet view article find links to article

pivot, the worst-case complexity of quickselect reduces from quadratic to linear, which is also the asymptotically optimal worst-case complexity of any selection

Tree sort (644 words) [view diff] no match in snippet view article find links to article

overhead, tree sort has few advantages over quicksort. It has better worst case complexity when a self-balancing tree is used, but even more overhead. Adding

Short integer solution problem (3,166 words) [view diff] no match in snippet view article find links to article

some randomly selected instances. For cryptography applications, worst case complexity is not sufficient, and we need to guarantee cryptographic construction

Hunt–Szymanski algorithm (972 words) [view diff] exact match in snippet view article find links to article

wiki engines, and molecular phylogenetics research software. The worst-case complexity for this algorithm is O(n2 log n), but in practice O(n log n) is

Fibonacci search technique (903 words) [view diff] exact match in snippet view article find links to article

search was first published. Fibonacci search has an average- and worst-case complexity of O(log n) (see Big O notation). The Fibonacci sequence has the

SAT solver (3,583 words) [view diff] exact match in snippet view article find links to article

problem in general. As a result, only algorithms with exponential worst-case complexity are known. In spite of this, efficient and scalable algorithms for

Shellsort (3,463 words) [view diff] exact match in snippet view article find links to article

(a1h1+a2h2)-sorted, for any nonnegative integers a1 and a2. The worst-case complexity of Shellsort is therefore connected with the Frobenius problem:

Sorting algorithm (6,477 words) [view diff] exact match in snippet view article find links to article

based on an algorithm with average time complexity (and generally worst-case complexity) O(n log n), of which the most common are heapsort, merge sort,

K-d tree (3,770 words) [view diff] exact match in snippet view article find links to article

algorithm that builds a balanced k-d tree to sort points has a worst-case complexity of O ( k n log ⁡ ( n ) ) {\displaystyle O(kn\log(n))} . This algorithm

Brodal queue (914 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Proportion extend sort (1,124 words) [view diff] case mismatch in snippet view article find links to article

"Generalized Leapfrogging Samplesort: A Class of O(n log22 n) Worst-Case Complexity and O(n log n) Average-Case Complexity Sorting Algorithms". arXiv:1801

Miklós Ajtai (632 words) [view diff] exact match in snippet view article find links to article

Tudományos Akadémia, Almanach, 1986, Budapest. Ajtai, Miklós (1998). "Worst-case complexity, average-case complexity and lattice problems". Documenta Mathematica:

Description logic (4,305 words) [view diff] no match in snippet view article find links to article

reasoning performance on typical inference problems even though the worst case complexity is no longer polynomial. From the mid '90s, reasoners were created

Cobham's thesis (685 words) [view diff] exact match in snippet view article find links to article

empirical algorithmic complexity for instances with 50–10,000 variables is O((log n)2) despite having exponential worst-case complexity estimate in theory.

Simplex algorithm (6,259 words) [view diff] exact match in snippet view article find links to article

and Minty gave an example, the Klee–Minty cube, showing that the worst-case complexity of simplex method as formulated by Dantzig is exponential time.

Art Gallery Theorems and Algorithms (641 words) [view diff] exact match in snippet view article find links to article

describe algorithms that perform well on random inputs despite poor worst-case complexity, reviewer Wm. Randolph Franklin recommends it "for the library of

Iterative deepening A* (1,405 words) [view diff] exact match in snippet view article find links to article

repeated expansions lead to severe performance degradation, with a worst-case complexity reaching Ω ( 2 2 N ) {\displaystyle \Omega (2^{2N})} , where N {\displaystyle

Cron (3,269 words) [view diff] no match in snippet view article find links to article

algorithms", good behavior given non-uniform time distributions, and worst case complexity θ ( n ) {\displaystyle \theta \left({\sqrt {n}}\right)} , "n" being

Triangular network coding (454 words) [view diff] exact match in snippet view article find links to article

The receiver now only needs to perform back-substitution, with worst-case complexity given as O ( n 2 ) {\displaystyle O(n^{2})} for each bit location

Christofides algorithm (1,404 words) [view diff] exact match in snippet view article find links to article

result; as such, the heuristic can give several different paths. The worst-case complexity of the algorithm is dominated by the perfect matching step, which

Occurs check (875 words) [view diff] no match in snippet view article find links to article

structures and looping. By not performing the occurs check, the worst case complexity of unifying a term t 1 {\displaystyle t_{1}} with term t 2 {\displaystyle

Bubble sort (2,354 words) [view diff] exact match in snippet view article find links to article

fairly well, but it retains O ( n 2 ) {\displaystyle O(n^{2})} worst-case complexity. Comb sort compares elements separated by large gaps, and can move

Painter's algorithm (1,467 words) [view diff] exact match in snippet view article find links to article

Assuming an optimal sorting algorithm, painter's algorithm has a worst-case complexity of O(n log n + m*n), where n is the number of polygons and m is

Algebraic geometry (7,498 words) [view diff] exact match in snippet view article find links to article

polynomials which is also doubly exponential. However, this is only a worst-case complexity, and the complexity bound of Lazard's algorithm of 1979 may frequently

Luus–Jaakola (1,113 words) [view diff] exact match in snippet view article find links to article

can be a Banach space, according to Kantorovich's analysis). The worst-case complexity of minimization on the class of unimodal functions grows exponentially

Quickselect (1,189 words) [view diff] exact match in snippet view article find links to article

in the real world. However, contrived sequences can still cause worst-case complexity; David Musser describes a "median-of-3 killer" sequence that allows

Sort (C++) (1,229 words) [view diff] exact match in snippet view article

significantly faster than other algorithms like heap sort with optimal worst-case complexity, and where the worst-case quadratic complexity rarely occurs. The

Binomial heap (2,566 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

DSatur (769 words) [view diff] exact match in snippet view article find links to article

{\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}} . The worst-case complexity of DSatur is O ( n 2 ) {\displaystyle O(n^{2})} , where n {\displaystyle

Safe and Sophie Germain primes (2,777 words) [view diff] exact match in snippet view article find links to article

a conjecture about Sophie Germain primes is used to lower the worst-case complexity from O(log12n) to O(log6n). A later version of the paper is shown

Protein fragment library (1,295 words) [view diff] no match in snippet view article find links to article

and up to four dihedral angles for each side chain, leading to a worst case complexity of k6*n possible states of the protein, where n is the number of

Timsort (2,908 words) [view diff] exact match in snippet view article find links to article

Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). "On the worst-case complexity of TimSort". In Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds

Binary search tree (3,088 words) [view diff] exact match in snippet view article find links to article

linked list (or "unbalanced tree") like structure, thus has the same worst-case complexity as a linked list.: 299-302 Binary search trees are also a fundamental

C++ Standard Library (1,526 words) [view diff] exact match in snippet view article find links to article

was introduced to allow both fast average performance and optimal worst-case complexity, and as of C++11, sorting is guaranteed to be at worst linearithmic

Leftist tree (2,357 words) [view diff] exact match in snippet view article find links to article

can exist, such as in the weight-biased leftist tree. The exact worst-case complexity of both types of leftist trees is 2 log2 n, counting comparisons

Heap (data structure) (2,929 words) [view diff] exact match in snippet view article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Neighbor joining (2,881 words) [view diff] exact match in snippet view article find links to article

always; "relax NJ" performs a hill-climbing search and retains the worst-case complexity of O(n^3). Rapid NJ is faster than plain relaxed NJ. FastME is an

Convex hull algorithms (2,326 words) [view diff] exact match in snippet view article find links to article

convex hull algorithm run in linear expected time, even if the worst-case complexity of the convex hull algorithm is quadratic in n. The discussion above

Tree traversal (2,894 words) [view diff] exact match in snippet view article find links to article

{\displaystyle n,} 1 step for edge up and 1 for edge down. The worst-case complexity is O ( h ) {\displaystyle {\mathcal {O}}(h)} with h {\displaystyle

Pairing heap (2,270 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Matching wildcards (1,534 words) [view diff] exact match in snippet view article find links to article

with the ABORT modification they perform acceptably in terms of worst-case complexity. On strings without * they take linear-to-string-size time to match

Fibonacci heap (3,785 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Numerical semigroup (1,419 words) [view diff] exact match in snippet view article find links to article

{a1, a2, a3} where a1 < a2 < a3 and gcd ( a1, a2, a3) = 1. Its worst-case complexity is not as good as Greenberg's algorithm but it is much simpler to

Joos Ulrich Heintz (1,048 words) [view diff] no match in snippet view article find links to article

collaborators demonstrated that under fragile and natural assumptions, the worst case complexity of elimination algorithms is unavoidably exponential, independent

Nearest neighbor search (3,341 words) [view diff] no match in snippet view article find links to article

complexity is O(log N) in the case of randomly distributed points, worst case complexity is O(kN^(1-1/k)) Alternatively the R-tree data structure was designed

Gaussian elimination (4,369 words) [view diff] exact match in snippet view article find links to article

Farebrother 1988, p. 12 Fang, Xin Gui; Havas, George (1997). "On the worst-case complexity of integer Gaussian elimination". Proceedings of the 1997 international

Grover's algorithm (4,691 words) [view diff] exact match in snippet view article find links to article

algorithm. The current theoretical best algorithm, in terms of worst-case complexity, for 3SAT is one such example. Generic constraint satisfaction problems

A* search algorithm (5,547 words) [view diff] exact match in snippet view article find links to article

fewer nodes than C ∗ {\textstyle C^{*}} in the worst case. The worst-case complexity of A* is often described as O ( b d ) {\textstyle O(b^{d})} , where

DFA minimization (3,043 words) [view diff] exact match in snippet view article find links to article

{\displaystyle {\overline {M}}} for the original M {\displaystyle M} . The worst-case complexity of Brzozowski's algorithm is exponential in the number of states

Boolean satisfiability problem (5,112 words) [view diff] exact match in snippet view article find links to article

the SAT problem is NP-complete, only algorithms with exponential worst-case complexity are known for it. In spite of this, efficient and scalable algorithms

Priority queue (5,009 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Binary heap (5,127 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Merge sort (6,727 words) [view diff] no match in snippet view article find links to article

quicksort does in its average case, and in terms of moves, merge sort's worst case complexity is O(n log n) - the same complexity as quicksort's best case. Merge

Lattice problem (3,660 words) [view diff] exact match in snippet view article find links to article

problem was NP-hard and discovered some connections between the worst-case complexity and average-case complexity of some lattice problems. Building on

Disjoint-set data structure (4,634 words) [view diff] exact match in snippet view article find links to article

Leeuwen also developed one-pass Find algorithms that retain the same worst-case complexity but are more efficient in practice. These are called path splitting

Heapsort (5,718 words) [view diff] exact match in snippet view article find links to article

original (PDF) on 27 December 2016. Wegener, Ingo (March 1992). "The worst-case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than

Matrix multiplication algorithm (4,483 words) [view diff] exact match in snippet view article find links to article

doi:10.1016/S0747-7171(08)80013-2 Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite

Coin problem (3,743 words) [view diff] no match in snippet view article find links to article

algorithm whose time complexity is currently an open problem. The worst case complexity has an upper bound which can be given in terms of the Frobenius

Graph coloring (8,459 words) [view diff] exact match in snippet view article find links to article

repeated on the remaining subgraph until no vertices remain. The worst-case complexity of DSatur is O ( n 2 ) {\displaystyle O(n^{2})} , where n {\displaystyle

Skew binomial heap (2,409 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Determinant (14,395 words) [view diff] exact match in snippet view article find links to article

2016, §1.1 Rote 2001 Fang, Xin Gui; Havas, George (1997). "On the worst-case complexity of integer Gaussian elimination" (PDF). Proceedings of the 1997

K-sorted sequence (1,581 words) [view diff] exact match in snippet view article find links to article

Par-optimal, that is, there exists no sequential algorithm with a better worst-case complexity. @rk. "Announcing Snowflake". Twitter blog. Retrieved 26 April 2021

Linear temporal logic to Büchi automaton (2,608 words) [view diff] exact match in snippet view article find links to article

reachability into account and may produce a smaller automaton but the worst-case complexity remains the same. The nodes of the graph are labeled by sets of

Matroid oracle (4,287 words) [view diff] exact match in snippet view article find links to article

MR 1337446. Hausmann, Dirk; Korte, Bernhard (1978), "Lower bounds on the worst-case complexity of some oracle algorithms", Discrete Mathematics, 24 (3): 261–276

Gröbner basis (10,036 words) [view diff] exact match in snippet view article find links to article

1 ) = D O ( n ) . {\displaystyle O(D^{n})^{O(1)}=D^{O(n)}.} The worst-case complexity of a Gröbner basis computation is doubly exponential in n. More

Factorization of polynomials over finite fields (4,620 words) [view diff] exact match in snippet view article find links to article

algorithm). The existence of a deterministic algorithm with a polynomial worst-case complexity is still an open problem. Like distinct-degree factorization algorithm

Clique problem (9,905 words) [view diff] exact match in snippet view article find links to article

for instance, Tarjan & Trojanowski (1977), an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with

Comparison of data structures (1,345 words) [view diff] exact match in snippet view article find links to article

indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names

Vincent's theorem (8,103 words) [view diff] no match in snippet view article find links to article

this date, it is the fastest bisection method. It has the same worst case complexity as Sturm's algorithm, but is almost always much faster. It has been