An asymptotic theory for recurrence relations based on minimization and maximization.

DOI10.1016/S0304-3975(02)00066-XzbMath1044.68168MaRDI QIDQ1401173

Tsung-Hsi Tsai, Hsien-Kuei Hwang

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Recurrence relationsOptimal algorithmsDivide-and-conquerPower-of-two rulesSlowly varying functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial inequalities (05A20) Recurrences (11B37)

Related Items

Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform ⋮ Operations research applications of dichotomous search ⋮ A General Framework for Static Cost Analysis of Parallel Logic Programs ⋮ Identities and periodic oscillations of divide-and-conquer recurrences splitting at half ⋮ Nearly subadditive sequences ⋮ On the cost of optimal alphabetic code trees with unequal letter costs ⋮ Binary trees with choosable edge lengths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mathematics for the Analysis of Algorithms.
• How evenly should one divide to conquer quickly?
• Exact balancing is not always good
• Binary trees and uniform distribution of traffic cutback
• Recurrence relations based on minimization and maximization
• A combinatorial problem in the design of electrical circuits
• Moment inequalities for random variables in computational geometry
• Search
• Asymptotic analysis of dichotomous search with search and travel costs
• Sur la fonction sommatoire de la fonction 'somme des chiffres'
• Recurrence relations based on minimization
• A note on the edges of the n-cube
• Queue-mergesort
• Mellin transforms and asymptotics: Digital sums
• Huffman algebras for independent random variables
• On polychotomous search problems
• A calculus for the random generation of labelled combinatorial structures
• Mellin transforms and asymptotics. The mergesort recurrence
• Probability theory of classical Euclidean optimization problems
• New primal and dual matching heuristics
• Bottom-up mergesort -- A detailed analysis
• A sorting function
• Solution of a Divide-and-Conquer Maximin Recurrence
• An Elementary Approach to Some Analytic Asymptotics
• Dichotomous Search for Random Objects on an Interval
• Improved master theorems for divide-and-conquer recurrences
• On a Greedy Heuristic for Complete Matching
• Some Maximal Solutions of the Generalized Subadditive Inequality
• The Number of 1’s in Binary Integers: Bounds and Extremal Properties
• A Discrete Search Game
• On the Optimality of Huffman Trees
• The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules
• Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence
• Optimum lopsided binary trees
• Multidimensional Divide-and-Conquer Maximin Recurrences
• A Linear Search Problem
• Some Theorems on Sorting
• A sorting problem and its complexity
• The probabilities of rooted tree-shapes generated by random bifurcation
• On dichotomous search with direction-dependent costs for a uniformly hidden object