Probabilistic recurrence relations

DOI10.1145/195613.195632MaRDI QIDQ4327630zbMATH OpenOpenAlexFDO

Authors Richard Karp

Publication date 10 April 1995

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195613.195632

zbMATH Keywords

divide-and-conquer algorithmsgambling games

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Probabilistic recurrence relations revisited
• (Probabilistic) recurrence relations revisited
• The solution of linear probabilistic recurrence relations
• Exact asymptotics of divide-and-conquer recurrences
• A simple expected running time analysis for randomized ``divide and conquer algorithms

Cited in

(17)

• Probabilistic recurrence relations revisited
• Computing expected runtimes for constant probability programs
• A simple expected running time analysis for randomized ``divide and conquer algorithms
• Concentrated hitting times of randomized search heuristics with variable drift
• A real elementary approach to the master recurrence and generalizations
• Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops
• scientific article; zbMATH DE number 1222139 (Why is no real title available?)
• (Probabilistic) recurrence relations revisited
• Nearly work-efficient parallel algorithm for digraph reachability
• An efficient distributed algorithm for constructing small dominating sets
• Recursive methods in probability control
• Tail bounds on hitting times of randomized search heuristics using variable drift analysis
• Verified analysis of random binary tree structures
• Optimal algorithms for finding connected components of an unknown graph
• Automated tail bound analysis for probabilistic recurrence relations
• Distributed algorithms for covering, packing and maximum weighted matching
• Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform

This page was built for publication: Probabilistic recurrence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4327630)