Amortized Computational Complexity

DOI10.1137/0606031zbMath0599.68046OpenAlexW1987927249WikidataQ56172073 ScholiaQ56172073MaRDI QIDQ3735083

Publication date: 1985

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0606031

zbMATH Keywords

survey complexity measure amortization averaging over time complexity analysis of data structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Efficient dual simplex algorithms for the assignment problem, The list update problem and the retrieval of sets, Average cost of Duval's algorithm for generating Lyndon words, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, ATLAS: automated amortised complexity analysis of self-adjusting data structures, The pairing heap: A new form of self-adjusting heap, Semi-dynamic shortest paths and breadth-first search in digraphs, Simple confluently persistent catenable lists, Lower bounds for monotonic list labeling, Fast meldable priority queues, Selectively-amortized resource bounding, Amortized efficiency of a path retrieval data structure, Fractional cascading. I: A data structuring technique, Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study, Rank-Balanced Trees, On top-down splaying, A data structure for arc insertion and regular path finding, Batch RSA, Complexity and resource bound analysis of imperative programs using difference constraints, Type-based cost analysis for lazy functional languages, Finding paths and deleting edges in directed acyclic graphs, Making data structures persistent, Splay trees as priority queues, A partially persistent data structure for the set-union problem, Connected component and simple polygon intersection searching, Topologically sweeping an arrangement, Can Burrows-Wheeler transform be replaced in chain code compression?, Worst-case analysis of the set-union problem with extended backtracking, An on-line graph coloring algorithm with sublinear performance ratio, Deletion without rebalancing in multiway search trees, Semi-online scheduling: a survey, Amortized Complexity Verified, Relaxed balance through standard rotations, A study on splay trees, Finding approximate repetitions under Hamming distance., Relaxed multi-way trees with group updates., Space-efficient functional offline-partially-persistent trees with applications to planar point location, Unnamed Item, On-line convex planarity testing, On-line graph algorithms for incremental compilation, Exponential automatic amortized resource analysis, Dynamic fractional cascading, Simplified linear-time Jordan sorting and polygon clipping, Dynamic maintenance of directed hypergraphs, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, A pointer-free data structure for merging heaps and min-max heaps, Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class, Lower bounds for planar orthogonal drawings of graphs, On-line computation of minimal and maximal length paths, Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits, Amortized complexity verified, Maintaining bridge-connected and biconnected components on-line, SIMPLE: An optimal disk system with two restricted heads, On the deque conjecture for the splay algorithm, Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and \(N\)-step SCAN, A generic arc-consistency algorithm and its specializations, Sensitivity analysis for Horn formulae, Complexity of algorithm and operations on trees, Chain-splay trees, or, how to achieve and prove \(\log \log N\)-competitiveness by splaying, AVL trees with relaxed balance, A generalization of maximal independent sets, The CB tree: a practical concurrent self-adjusting search tree, The weighted list update problem and the lazy adversary, A systematic analysis of splaying, On sorting, heaps, and minimum spanning trees, Dynamic algorithms for classes of constraint satisfaction problems, Partially dynamic maintenance of minimum weight hyperpaths, A dynamic location problem for graphs, The list update problem and the retrieval of sets, Most uniform path partitioning and its use in image processing, The derivation of a tighter bound for top-down skew heaps, Efficient Type-Checking for Amortised Heap-Space Analysis, A tight amortized bound for path reversal, On the sequential access theorem and deque conjecture for splay trees, On-line algorithms for networks of temporal constraints, Heaps and heapsort on secondary storage, New results on competitive analysis of online SRPT scheduling, A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY, VARIANTS OF (A,B)-TREES WITH RELAXED BALANCE, Maintaining a topological order under edge insertions, Semi-dynamic breadth-first search in digraphs, Incremental convex planarity testing, Preprocessing of intractable problems, Manipulating multiple stacks with ordered-heap, Efficient token-based control in rings., The set union problem with dynamic weighted backtracking, Efficient management of dynamic tables, Sequential access in splay trees takes linear time, Two decades of automatic amortized resource analysis, Type-based analysis of logarithmic amortised complexity, Maintaining longest paths incrementally, The amortized complexity of Henriksen's algorithm

Cites Work