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