Find link

language:

Find link is a tool written by Edward Betts.

searching for Space complexity 108 found (270 total)

Game complexity (2,837 words) [view diff] exact match in snippet view article find links to article

Combinatorial game theory measures game complexity in several ways: State-space complexity (the number of legal game positions from the initial position) Game

State space (computer science) (933 words) [view diff] no match in snippet view article

In computer science, a state space is a discrete space representing the set of all possible configurations of a system. It is a useful abstraction for

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

number of pixels to be filled. The painter's algorithm's worst-case space-complexity is O(n+m), where n is the number of polygons and m is the number of

Neil Immerman (332 words) [view diff] exact match in snippet view article find links to article

the Immerman–Szelepcsényi theorem, the result that nondeterministic space complexity classes are closed under complementation. Immerman is an ACM Fellow

Top-down parsing (1,368 words) [view diff] exact match in snippet view article find links to article

the number and contents of each stack, thereby reducing the time and space complexity of the parser. This leads to an algorithm known as Generalized LL parsing

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

machine in polynomial space. EXPTIME relates to the other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME

Nondeterministic algorithm (382 words) [view diff] exact match in snippet view article find links to article

complexity classes based on nondeterministic time and nondeterministic space complexity. They may be simulated using nondeterministic programming, a method

Solving chess (1,540 words) [view diff] exact match in snippet view article find links to article

least weakly. Calculated estimates of game-tree complexity and state-space complexity of chess exist which provide a bird's eye view of the computational

Immerman–Szelepcsényi theorem (1,272 words) [view diff] exact match in snippet view article find links to article

theory, the Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation. It was proven independently

Teknomo–Fernandez algorithm (1,258 words) [view diff] exact match in snippet view article find links to article

fact that L {\displaystyle L} will probably not exceed 6 reduces the space complexity to O ( R F ) {\displaystyle O(RF)} . The entire algorithm runs in O

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

traditionally measured on a deterministic Turing machine. Several important space complexity classes are sublinear, that is, smaller than the size of the input

NESL (263 words) [view diff] exact match in snippet view article find links to article

flattening transform, however, can increase the asymptotic work and space complexity of the original program, leading to a much less efficient result. NESL

Best, worst and average case (1,273 words) [view diff] exact match in snippet view article find links to article

when implemented with the "shortest first" policy, the worst-case space complexity is instead bounded by O(log(n)). Heapsort has O(n) time when all elements

Noga Alon (1,336 words) [view diff] exact match in snippet view article find links to article

S2CID 208936467. Alon, Noga; Matias, Yossi; Szegedy, Mario (1999). "The space complexity of approximating the frequency moments". Journal of Computer and System

Fanorona (823 words) [view diff] exact match in snippet view article find links to article

complexity and state-space complexity can be computed. Fanorona has a game-tree complexity of ~1046 and a state-space complexity of ~1021. In 2007, the

Schreier vector (520 words) [view diff] exact match in snippet view article find links to article

group theory, a Schreier vector is a tool for reducing the time and space complexity required to calculate orbits of a permutation group. Suppose G is a

Space hierarchy theorem (2,784 words) [view diff] exact match in snippet view article find links to article

The hierarchy theorems are used to demonstrate that the time and space complexity classes form a hierarchy where classes with tighter bounds contain

Yen's algorithm (2,179 words) [view diff] no match in snippet view article find links to article

In graph theory, Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost. The algorithm was published

Potential method (1,799 words) [view diff] exact match in snippet view article find links to article

potential method is a method used to analyze the amortized time and space complexity of a data structure, a measure of its performance over sequences of

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

the number of unoccupied spaces before a move. However, the state-space complexity is largely unchanged, since any legal position in one game will also

Gödel Prize (2,163 words) [view diff] exact match in snippet view article find links to article

1137/S0097539796307698 Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments" (PDF), Journal of Computer

Streaming algorithm (3,608 words) [view diff] exact match in snippet view article find links to article

be the ⁠ S 1 ∗ S 2 {\displaystyle S_{1}*S_{2}} ⁠. Hence the total space complexity the algorithm takes is of the order of O ( k log ⁡ 1 ε λ 2 n 1 − 1

CURE algorithm (788 words) [view diff] exact match in snippet view article find links to article

) {\displaystyle O(n^{2}\log n)} , making it rather expensive, and space complexity is O ( n ) {\displaystyle O(n)} . The algorithm cannot be directly

M-ary tree (2,761 words) [view diff] exact match in snippet view article find links to article

locality of reference, particularly during a preorder traversal. The space complexity of this method is O ( m n ) {\displaystyle O(m^{n})} . Each node would

Juris Hartmanis (2,513 words) [view diff] exact match in snippet view article find links to article

has deterministic space complexity (log n)2, which contained the essential idea that led to Savitch's theorem on space complexity. Hartmanis continued

Complexity (4,498 words) [view diff] exact match in snippet view article find links to article

(usually measured in bits), using the most efficient algorithm, and the space complexity of a problem equal to the volume of the memory used by the algorithm

List of terms relating to algorithms and data structures (3,135 words) [view diff] exact match in snippet view article find links to article

asymptotically tight bound asymptotic bound asymptotic lower bound asymptotic space complexity asymptotic time complexity asymptotic upper bound augmenting path automaton

Counting points on elliptic curves (2,454 words) [view diff] exact match in snippet view article find links to article

{\displaystyle M(n)} denotes the complexity of integer multiplication. Its space complexity is O ( n 3 ) {\displaystyle O(n^{3})} . In the 1990s, Noam Elkies,

Run-length encoding (1,340 words) [view diff] exact match in snippet view article find links to article

primarily white space, with occasional interruptions of black. RLE has a space complexity of ⁠ O ( n ) {\displaystyle O(n)} ⁠, where n is the size of the input

Skolem arithmetic (1,957 words) [view diff] exact match in snippet view article find links to article

powers of theories. They apply this method to obtain triply exponential space complexity for ( N ∗ , + ¯ ) {\displaystyle (N^{*},{\bar {+}})} , and thus of

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

algorithms are determined by the time complexity of queries as well as the space complexity of any search data structures that must be maintained. The informal

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

the database is permanently in the memory. Also, both the time and space complexity of this algorithm are very high: O ( 2 | D | ) {\displaystyle O\left(2^{|D|}\right)}

Sweep line algorithm (502 words) [view diff] exact match in snippet view article find links to article

N segments in the plane in time complexity of O((N + K) log N) and space complexity of O(N). Since then, this approach has been used to design efficient

Kendall rank correlation coefficient (5,437 words) [view diff] exact match in snippet view article find links to article

These algorithms have O ( 1 ) {\displaystyle O(1)} update time and space complexity, scaling efficiently with the number of observations. Consequently

Cook–Levin theorem (2,355 words) [view diff] exact match in snippet view article find links to article

to encode computation with a Turing machine limited to polynomial space complexity, proving that there exists a problem (the recognition of true quantified

Baby-step giant-step (1,061 words) [view diff] exact match in snippet view article find links to article

does not slow down the overall baby-step giant-step algorithm. The space complexity of the algorithm is O ( n ) {\displaystyle O({\sqrt {n}})} , while

Baby-step giant-step (1,061 words) [view diff] exact match in snippet view article find links to article

does not slow down the overall baby-step giant-step algorithm. The space complexity of the algorithm is O ( n ) {\displaystyle O({\sqrt {n}})} , while

Differentiable neural computer (801 words) [view diff] exact match in snippet view article find links to article

Refinements include sparse memory addressing, which reduces time and space complexity by thousands of times. This can be achieved by using an approximate

Reef Ball Foundation (1,256 words) [view diff] no match in snippet view article find links to article

ISSN 1675-5820. Sherman, RL (2002). "Artificial reef design: void space, complexity, and attractants" (PDF). ICES Journal of Marine Science. 59. International

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

reduction, but also in the realm of real-world computation in time (or space) complexity analysis of algorithms, where it assumes the form of e.g. polynomial-time

Sieve of Eratosthenes (3,043 words) [view diff] exact match in snippet view article find links to article

{\displaystyle (k\Delta +1)^{2}>(k+1)\Delta } . If Δ is chosen to be √n, the space complexity of the algorithm is O(√n), while the time complexity is the same as

NL-complete (659 words) [view diff] exact match in snippet view article find links to article

Addison-Wesley. ISBN 0-201-53082-1. Rytter, Wojciech (1986), "The space complexity of the unique decipherability problem", Information Processing Letters

Iterated logarithm (746 words) [view diff] exact match in snippet view article find links to article

algorithms and computational complexity, appearing in the time and space complexity bounds of some algorithms such as: Finding the Delaunay triangulation

Append (717 words) [view diff] exact match in snippet view article find links to article

completely copy all of its arguments except the last, both its time and space complexity are O(n) for a list of n {\displaystyle n} elements. It may thus be

Cognitive strategy (405 words) [view diff] exact match in snippet view article find links to article

may have very different characteristics in terms of their time and space complexity, memory requirements, etc., and therefore in terms of their error characteristics

Universal Turing machine (2,957 words) [view diff] no match in snippet view article find links to article

using Donald Knuth's Big O notation. The corresponding result for space-complexity rather than time-complexity is that we can simulate in a way that uses

Director string (675 words) [view diff] exact match in snippet view article find links to article

time complexity of finding the free variables in t is traded for the space complexity of maintaining a list of the terms in which a variable occurs. Although

Yossi Matias (952 words) [view diff] case mismatch in snippet view article find links to article

Award". Alon, Noga; Matias, Yossi; Szegedy, Mario (1999-02-01). "The Space Complexity of Approximating the Frequency Moments". Journal of Computer and System

Array (data structure) (3,412 words) [view diff] exact match in snippet view article

data structures), requiring little space overhead, but may have poor space complexity, particularly when modified, compared to tree-based data structures

Rope (data structure) (1,779 words) [view diff] exact match in snippet view article

structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n). In summary, ropes are preferable

Advanced Encryption Standard (5,675 words) [view diff] exact match in snippet view article find links to article

computers on the planet in 2016. A paper in 2015 later improved the space complexity to 256 bits, which is 9007 terabytes (while still keeping a time complexity

Space–time tradeoff (738 words) [view diff] exact match in snippet view article find links to article

Savitch's theorem – Relation between deterministic and nondeterministic space complexity Hellman, Martin (July 1980). "A Cryptanalytic Time-Memory Tradeoff"

Speck (cipher) (2,411 words) [view diff] exact match in snippet view article

attack model) Variant Rounds attacked Time complexity Data complexity Space complexity Attack type Speck128/256 25/34 (74%) 2253.35 2125.35 222 differential

Bentley–Ottmann algorithm (3,312 words) [view diff] exact match in snippet view article find links to article

priority queues such as a Fibonacci heap are not necessary. Note that the space complexity of the priority queue depends on the data structure used to implement

Package-merge algorithm (828 words) [view diff] exact match in snippet view article find links to article

Methods involving graph theory have been shown to have better asymptotic space complexity than the package-merge algorithm, but these have not seen as much practical

Bentley–Ottmann algorithm (3,312 words) [view diff] exact match in snippet view article find links to article

priority queues such as a Fibonacci heap are not necessary. Note that the space complexity of the priority queue depends on the data structure used to implement

Tic-tac-toe (4,430 words) [view diff] exact match in snippet view article find links to article

or to enumerate the 765 essentially different positions (the state space complexity) or the 26,830 possible games up to rotations and reflections (the

Graph canonization (1,112 words) [view diff] exact match in snippet view article find links to article

MR 2475148. Arvind, V.; Das, Bireswar; Köbler, Johannes (2007), "The space complexity of k-tree isomorphism", Algorithms and Computation: 18th International

Memory-hard function (825 words) [view diff] case mismatch in snippet view article find links to article

Joel; Blocki, Jeremiah; Pietrzak, Krzysztof (2017-07-07). "Sustained Space Complexity". arXiv:1705.05313 [cs.CR]. Blocki, Jeremiah; Liu, Peiyuan; Ren, Ling;

Dijkstra's algorithm (5,645 words) [view diff] exact match in snippet view article find links to article

per node is bounded by b, then the algorithm's worst-case time and space complexity are both in O(b1+⌊C* ⁄ ε⌋). Further optimizations for the single-target

Tarjan's strongly connected components algorithm (1,711 words) [view diff] case mismatch in snippet view article find links to article

it is on the stack, and performing this test by examining the flag. Space Complexity: The Tarjan procedure requires two words of supplementary data per

Parsing (4,881 words) [view diff] exact match in snippet view article find links to article

direct and indirect left-recursion and may require exponential time and space complexity while parsing ambiguous context-free grammars, more sophisticated algorithms

Real RAM (826 words) [view diff] exact match in snippet view article find links to article

basic unit of computation involves one bit. Therefore, the time and space complexity of numeric algorithms depends on the number of bits needed to represent

David Mount (1,043 words) [view diff] exact match in snippet view article find links to article

} , and forms a data structure that can be stored efficiently (low space complexity) and that returns the ( 1 + ϵ ) {\displaystyle (1+\epsilon )} -approximate

Single-linkage clustering (2,496 words) [view diff] exact match in snippet view article find links to article

algorithm with time complexity O ( n 2 ) {\displaystyle O(n^{2})} and space complexity O ( n ) {\displaystyle O(n)} (both optimal) known as SLINK. The slink

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

We will show in the following section that we can improve upon the space complexity. Sum of histories is a technique introduced by physicist Richard Feynman

Real closed field (2,982 words) [view diff] exact match in snippet view article find links to article

big Omega notation. This shows that both the time complexity and the space complexity of quantifier elimination are intrinsically double exponential. For

Giovanni Pighizzini (358 words) [view diff] exact match in snippet view article find links to article

to the computational complexity theory by results on sublogarithmic space complexity classes and on the complexity of searching for a lexicographically

Use-define chain (1,413 words) [view diff] exact match in snippet view article find links to article

simple but powerful concept: theoretical and practical results in space complexity theory, access complexity(I/O complexity), register allocation and

Viliam Geffert (313 words) [view diff] exact match in snippet view article find links to article

University, Comenius University Known for state complexity, small-space complexity Scientific career Fields Automata theory, computational complexity

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

statistics based algorithms typically have constant update time and space complexity, but have different error bound guarantees compared to computer science

Compressed cover tree (1,320 words) [view diff] exact match in snippet view article find links to article

Name of datastructure, source Claimed time complexity Claimed space complexity Proof of result Navigating nets O ( 2 O ( dim ) ⋅ | R | ⋅ log ⁡ ( Δ ( R

Sequence assembly (2,944 words) [view diff] exact match in snippet view article find links to article

(known as repeats) which can, in the worst case, increase the time and space complexity of algorithms quadratically; DNA read errors in the fragments from

Persistent array (1,571 words) [view diff] exact match in snippet view article find links to article

The following theorem shows that under mild assumptions about the space complexity of the array, lookups must take Ω ( log ⁡ log ⁡ n ) {\displaystyle

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

algorithm to have a worst-case time complexity of O(mn log m) and space complexity of O(mn), though it regularly beats the worst case with typical inputs

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

sequential access, not random access. However, it has additional O(n) space complexity and involves a large number of copies in simple implementations. Merge

Rooted graph (1,821 words) [view diff] exact match in snippet view article find links to article

graph is important in the study of game complexity, where the state-space complexity is the number of vertices in the graph. The number of rooted undirected

Go (game) (16,296 words) [view diff] exact match in snippet view article

can be difficult to estimate. The number of legal positions (state-space complexity) for chess has been estimated at anywhere between 1043 and 1050; in

Distance matrix (4,098 words) [view diff] exact match in snippet view article find links to article

calculations done after every cluster to update the distance matrix Space complexity is O ( N 2 ) {\displaystyle O(N^{2})} Distance metrics are a key part

Priority queue (4,953 words) [view diff] no match in snippet view article find links to article

structures, such as with third-party or standard libraries. From a space-complexity standpoint, using self-balancing binary search tree with linked list

S/KEY (1,298 words) [view diff] exact match in snippet view article find links to article

264, which can be pre-calculated with the same amount of space. The space complexity can be optimized by storing chains of values, although collisions might

Lambda calculus (11,765 words) [view diff] exact match in snippet view article find links to article

during reduction. It is not currently known what a good measure of space complexity would be. An unreasonable model does not necessarily mean inefficient

Sardinas–Patterson algorithm (1,375 words) [view diff] exact match in snippet view article find links to article

doi:10.1016/0020-0190(84)90020-6.. Rytter, Wojciech (1986). "The space complexity of the unique decipherability problem". Information Processing Letters

Spatial verification (642 words) [view diff] case mismatch in snippet view article find links to article

uncertainty in the model space Represent uncertainty in the image space Complexity Lineal complexity in the number of correspondences and the number of

Multiple sequence alignment (6,213 words) [view diff] exact match in snippet view article find links to article

that by using decision diagrams, MSA may be modeled in polynomial space complexity. The most widely used approach to multiple sequence alignments uses

Trachtenberg system (6,356 words) [view diff] exact match in snippet view article find links to article

to achieve multiplications a × b {\displaystyle a\times b} with low space complexity, i.e. as few temporary results as possible to be kept in memory. This

Suffix array (3,844 words) [view diff] exact match in snippet view article find links to article

initial positions of the suffixes are stored in the array to reduce the space complexity since the suffixes are too large. lcp array lcp[1,...n]: It is an array

Knapsack problem (7,770 words) [view diff] exact match in snippet view article find links to article

n / 2 ) {\displaystyle O^{*}(2^{n/2})} time with a slightly worse space complexity of O ∗ ( 2 n / 4 ) {\displaystyle O^{*}(2^{n/4})} . As for most NP-complete

Association rule learning (6,709 words) [view diff] exact match in snippet view article find links to article

Furthermore it will almost certainly use less memory as DFS has a lower space complexity than BFS. To illustrate this, let there be a frequent itemset {a, b

Time hierarchy theorem (2,505 words) [view diff] exact match in snippet view article find links to article

relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of computational

Hex (board game) (4,402 words) [view diff] exact match in snippet view article

positions on a board of a particular size. In 11×11 Hex, the state space complexity is approximately 2.4×1056; versus 4.6×1046 for chess. The game tree

Held–Karp algorithm (2,164 words) [view diff] exact match in snippet view article find links to article

length of the shortest cycle is needed, not the cycle itself, then space complexity can be improved somewhat by noting that calculating g ( S , e ) {\displaystyle

Fisher–Yates shuffle (5,048 words) [view diff] exact match in snippet view article find links to article

merge recursively to give the shuffled array. The asymptotic time and space complexity of the Fisher–Yates shuffle are optimal. Combined with a high-quality

Maximum subarray problem (2,467 words) [view diff] exact match in snippet view article find links to article

complexity of Kadane's algorithm is O ( n ) {\displaystyle O(n)} and its space complexity is O ( 1 ) {\displaystyle O(1)} . Similar problems may be posed for

Connected-component labeling (3,190 words) [view diff] exact match in snippet view article find links to article

generalized to arbitrary dimensions, albeit with increased time and space complexity. This is a fast and very simple method to implement and understand

True quantified Boolean formula (3,769 words) [view diff] exact match in snippet view article find links to article

1145/146585.146609. S2CID 315182. Arora, Sanjeev; Barak, Boaz (2009), "Space complexity", Computational Complexity, Cambridge: Cambridge University Press,

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

complexity is estimated to be around 10^107. Its upper bound state-space complexity is ~10^40. Freeling features Dameo as one of his core six games on

Flattening transformation (428 words) [view diff] exact match in snippet view article find links to article

to segmented scan. Flattening can increase the asymptotic work and space complexity of the original program, leading to a much less efficient result. Flattening

Count sketch (1,466 words) [view diff] exact match in snippet view article find links to article

Farach-Colton 2004. Alon, Noga, Yossi Matias, and Mario Szegedy. "The space complexity of approximating the frequency moments." Journal of Computer and system

Haskell features (3,537 words) [view diff] exact match in snippet view article find links to article

nearly optimal (for a list-based code) time complexity and very low space complexity achieved through telescoping multistage recursive production of primes:

Fractional cascading (3,868 words) [view diff] exact match in snippet view article find links to article

{\displaystyle L_{4}[3]=79} . However, this solution pays a high penalty in space complexity: it uses space O ( k n ) {\displaystyle O(kn)} as each of the n {\displaystyle

Existential theory of the reals (3,817 words) [view diff] exact match in snippet view article find links to article

algorithm that also has exponential time dependence, but only polynomial space complexity; that is, he showed that the problem could be solved in PSPACE. The

Operational transformation (5,313 words) [view diff] exact match in snippet view article find links to article

among the control algorithm and transformation functions, and time-space complexity of the OT system. Most existing OT control algorithms for concurrency

Book embedding (8,167 words) [view diff] exact match in snippet view article find links to article

solved in unambiguous logarithmic space (the analogue, for logarithmic space complexity, of the class UP of unambiguous polynomial-time problems). However

Leader election (4,409 words) [view diff] exact match in snippet view article find links to article

the size of the network. An optimal solution with O(n) message and space complexity is known. In this algorithm, processes have the following states: Dummy:

Product literature (2,426 words) [view diff] case mismatch in snippet view article find links to article

Proliferation Strategies and Firm Performance: The Moderating Role of Product Space Complexity". Strategic Management Journal. 34 (12): 1435–1452. doi:10.1002/smj

Re-Pair (1,230 words) [view diff] exact match in snippet view article find links to article

the data structures required to implement it with linear time and space complexity. The experiments showed that Re-Pair achieves high compression ratios

Array Based Queuing Locks (1,167 words) [view diff] exact match in snippet view article find links to article

of entries equal to the number of processors, resulting in linear space complexity. This is generally wasteful as it is rare that all processors would