Question

Design an algorithm that takes in a stream z1, . . . , zM of M integers in [n] and at any time t can output a uniformly random element in z1, . . . , zt . Your algorithm may use at most polynomial in log n and log M space. Prove the correctness and analyze the space complexity of your algorithm. Y

Answer 1

import random

def rand_select(*args):

selected = random.choice(args)

print( selected)

rand_select(12,32,43,54,2,34,65,2,64,74,97)

The space complexity of this program is O(1)

Step-by-step explanation:

The list of arguments to the function is assigned to the variable "args" and the random's choice method randomly picks an item and assigns it to the variable "selected", then the variable is printed out on the screen. The memory used is 1 + 1 = 2, which is a constant, therefore making the space complexity to be O(1).