English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we present a method for obtaining tail-bounds for randomvariables satisfying certain probabilistic recurrences that arise in theanalysis of randomized parallel divide and conquer algorithms. In suchalgorithms, some computation is initially done to process an input x, which isthen randomly split into subproblems $h_1(x), ..., h_n(x)$, and the algorithmproceeds recursively in parallel on each subproblem. The total work on input x,W(x), then satisfies a probabilistic recurrence of the form $W(x) = a(x) +\sum_{i=1}^n W (h_i(x))$, and the span (the longest chain of sequentialdependencies), satisfies $S(x) = b(x) + \max_{i=1}^n S(h_i(x))$, where a(x) andb(x) are the work and span to split x and combine the results of the recursivecalls.  Karp has previously presented methods for obtaining tail-bounds in the casewhen n = 1, and under certain stronger assumptions for the work-recurrence whenn > 1, but left open the question of the span-recurrence. We first show how toextend his technique to handle the span-recurrence. We then show that in somecases, the work-recurrence can be bounded under simpler assumptions than Karp'sby transforming it into a related span-recurrence and applying our firstresult. We demonstrate our results by deriving tail bounds for the work andspan of quicksort and the height of a randomly generated binary search tree.

Probabilistic Recurrence Relations for Work and Span of Parallel Algorithms