I am writing a paper in which the worst-case analysis of a certain randomized algorithm is correct with probability $1-1/n$ (where $n$ is the size of the problem). I find myself writing, time after time, the following sentence:
"With high probability, in the worst case, the performance of phase A is at most X".
The worst-case is with relation to the inputs; the high probability is with relation to the randomization of the algorithm. I.e, there is an adversary that choose the worst possible inputs, but then I do a lottery on which the adversary has no effect.
Since there are many phases, this sentence appears many times throughout the paper and it looks cumbersome. I tried to make it shorter by writing:
"In the worst case (WHP), the performance of phase A is at most... "
This still looks cumbersome... Is there a more common way to express this meaning?
