Find link

language:

Find link is a tool written by Edward Betts.

searching for space complexity 110 found (271 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

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

Painter's algorithm (1,467 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

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

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

Solving chess (1,542 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

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

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

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

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

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

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

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

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

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

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

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,762 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

Sweep line algorithm (513 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

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

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

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

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

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,

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,316 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)}

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,354 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

Reductionism (3,263 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

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

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

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

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

Universal Turing machine (2,963 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

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

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

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

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,787 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

Yossi Matias (960 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

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

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

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

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 (748 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"

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

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

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;

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

Dijkstra's algorithm (5,637 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

Real closed field (2,984 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

Monoque (211 words) [view diff] exact match in snippet view article find links to article

any particular machine the block list is O(1) in size and is an upper bound to O(lg(N)), it bounds the space complexity of the structure by a constant.

Hierarchical clustering (3,530 words) [view diff] exact match in snippet view article find links to article

datasets, limiting its scalability . (b) Scalability: Due to the time and space complexity, hierarchical clustering algorithms struggle to handle very large datasets

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

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

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

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

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

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

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

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

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

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

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

Go (game) (16,260 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

Sorting algorithm (6,537 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

Optimal binary search tree (2,965 words) [view diff] exact match in snippet view article find links to article

binary search trees was necessary since Knuth's algorithm time and space complexity can be prohibitive when n {\displaystyle n} is substantially large

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 (5,009 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,994 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

Suffix array (3,775 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

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

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

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

Log-space reduction (1,358 words) [view diff] exact match in snippet view article find links to article

( n ) {\displaystyle f(n)} is equivalent to a Turing machine with space complexity O ( log ⁡ f ( n ) ) {\displaystyle O(\log f(n))} . The most important

Knapsack problem (7,799 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

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

Fisher–Yates shuffle (5,222 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

Hex (board game) (4,408 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

Time hierarchy theorem (2,497 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

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

True quantified Boolean formula (3,846 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,

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

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

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

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

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

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:

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

Operational transformation (5,311 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

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

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

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