World's most popular travel blog for travel bloggers.

# Expected versus Randomized

, ,
Problem Detail:

Is there any difference between expected polynomial time and randomized polynomial time algorithm?

###### Answered By : Ami Tavory

RP (randomized polynomial time) is a complexity class for algorithms that always run in polynomial time, while possibly make truly random choices, and always rejecting correctly while usually accepting correctly (i.e., with probability greater than $\frac{1}{2}$).

Expected polynomial time usually means that the complexity is polynomial time only in expectation, and the answer is always correct.

Suppose you have the following (silly) algorithm to check if the first element, in an array with length n, is the maximum:

1. Scan the array, check if the first element is maximum.

2. With probability $\left(\frac{1}{2}\right)^n$, uselessly scan the array an additional $\frac{2^n}{n}$ times, and recheck the result of step 1.

3. Return the answer from 1 in any case.

This algorithm has expected polynomial time. The cost of the first step is $\Theta(n)$. The expected cost of the second step is $\Theta\left( \left(\frac{1}{2}\right)^n n \frac{2^n}{n}\right) = O(1)$. The cost of the third step is constant. Conversely, it is not in RP because the second step can run in time $\Theta\left( 2^n \right)$ for an unfortunate randomized outcome.