You have $m$ bins, and $n$ balls. Each time you throw a ball, it lands in one of the $m$

bins with probability $\frac{1}{m}.$ What is the expected number of bins that contain at least

$2$ balls?

In the code below, we define random $(n)$ which returns iin$[n]$ with probability $\frac{1}{n},$ in

$(1)-$time, and CoinFlip simply returns $0$ or $1,$ each with probability $\frac{1}{2}.$

import math

import random

# returns a random integer in $1,n$

def random$(n)$ :

return random. randint $(1,n)$

# returns a random integer in $,1$

def coinflip$()$:

return random$(2)-1$

For each function that follows, give each function's best case, worst case, and average

case asymptotic running times. Justify your answer.

$($a$)$

import random

import math

def $f1(xs)$ :

$s=$

$n=$len$(xs)$

$k=$random$(n)$

math.sqrt $(n))$

if $k=1$ :

$m=\frac{n}{\frac{?}{?}}2$

for $j$ in range $(m)$ :

$s**=xs[j]$

return $s$