The solution of linear probabilistic recurrence relations

DOI10.1007/S00453-002-1003-4MaRDI QIDQ1402216zbMATH OpenOpenAlexFDO

Authors Louay Bazzi, Sanjoy K. Mitter

Publication date 19 August 2003

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-002-1003-4

zbMATH Keywords

Divide-and-conquer algorithmsRandomized algorithmsRecurrence relations

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• Probabilistic recurrence relations revisited
• (Probabilistic) recurrence relations revisited
• A simple expected running time analysis for randomized ``divide and conquer algorithms
• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications

Cited in

(8)

• Probabilistic recurrence relations revisited
• Solutions of linear recurrence equations
• Computing expected runtimes for constant probability programs
• Proving divide and conquer complexities in Isabelle/HOL
• A simple expected running time analysis for randomized ``divide and conquer algorithms
• Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms
• Probabilistic recurrence relations
• (Probabilistic) recurrence relations revisited

This page was built for publication: The solution of linear probabilistic recurrence relations

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