We can test for primes in something like time O$($log$($n$)$

$12).$ Assume, perhaps unrealistically for anything but the RAM model, that we can compute $2$

n $1$ for any n in

time O$($log$($n$)).$ Assume f$\_0($n$)$ takes time O$($n

$24).$ Consider the following algorithm,

which takes a positive integer as input:

$1$ def function$($n$)$:

$2$ if is$\_$prime$(2**$n $-1)$:

$3$ return f$\_0($n$)$

What is the best upper and lower bound you can give on the asymptotic runtime of

the above algorithm,

$($a$)$ assuming LPWC is true? $($Use O$,,\backslash$Theta as appropriate.$)$

$($b$)$ assuming LPWC is false? $($Use O$,,\backslash$Theta as appropriate.$)$

$($c$)$ assuming LPWC remains unknown? $($Use O$,,\backslash$Theta as appropriate.$)$