Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound. For example, assuming you need to find the median of an array once every $n$ operations of type $X$ (which does not change the array).You could take a specific algorithm, such as the median of medians selection algorithm, which takes at most $c\cdot n$ time, and perform $c$ of its operations every time $X$ is performed.This guarantees that the worst case run time of finding the median in each $X$ call is constant.But now assume we'd like to use a randomized Las-Vegas algorithm (always correct, runtime is computed in expectation), such as computing the median by selection with random pivot.Now we know that the algorithm is expected to take $c'\cdot n$ operations, but it might take more, or less.How do you determine how many of the iterations you run every time $X$ is performed?Can we say that by performing, say, $2c'$ operations every time we will finish computing the median with high probability?Can we adaptively select how many operations of the selection algorithms to perform at each of $X_1,X_2\ldots X_n$ calls such that we will finish computing the median with probability $1$, but so that with high probability, the number of operations in each $X$ call is constant?
Deamortizing a Las-Vegas randomized algorithm
randomized algorithms;arrays;selection problem