Randomized Algorithms
basic prob
Problem 2
Input
Array A[1..2n] with n X's and n Y's
Output
index isuch that A[i] = X
Normal
loop the array
complexity O(n)
def find_X_slow(A):
for i in range(len(A)):
if A[i] == X:
return i
Evil user inputs
[yyyy...xxx]
def find_X(A):
for i in range(len(A)//2):
j = random.randint(0,len(A)-1):
if A[j] == x:
return j
find_X_slow
Claim
The average runtime for a fixed A is O(1)
Y_i, the runtime of the i-th iteration
