1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

Your second example looks fine to me. "In the worst case, phase A takes time/space X whp" is even shorter.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.