This question is about searching and solving a problem in modular arithmetic.

$($a$)$ Consider the following vector of integers:

$1,2,3,4,5,6,7$

By hand, directly run through the Binary Search algorithm on this vector

searching for the value $5.$ Show your working and how you choose elements to

inspect.

$($b$)$ It can be argued that the Binary Search algprithm is optimal. Very briefly explain

what this means. You do not have to provide an argument, just explain what the

statement means.

$($c$)$ A modular square root of a non$-$negative integer $y$ modulo $N$ is a non$-$negative

integer $x$ such that $x^2-=y(modN),$ i$.$e$.x^2$ and $y$ are congruent modulo $N.$ For

instance, if $y$ is $2$ and $N$ is $7,$ then $x$ could be $3$ since $9$ mod $7$ is $2,$ or $x$ could be $4$

since $16$ mod $7$ is also $2.$ That is$,$ there can be multiple square roots. $($There is a

short revision on modular arithmetic at the end of this question.$)$ The modular

square roots $x$ and $y$ are also assumed to be integers less than $N.$ Note that $N$ is

always assumed to be greater than $0.$

Consider the following piece of pseudocode that finds the smallest square root of

an integer $y$ modulo $N$ :

function RECMOD$(a,N)$

if RECMOD$(a-N,N)y,N0x$NRECMOD$(x^2,N)=$yxRECMOD$(a,N)O(\frac{a}{N})aNa$ then

return $a$

end $if$

return RECMOD$(a-N,N)$

end function

function MODSQUAREROOT$(y,N)$

for $0xNdo$

$if$ RECMOD$(x^2,N)=y$ then

return $x$

end $if$

end for

end function

$i.$ Briefly explain why the worst$-$case time complexity $of$ RECMOD$(a,N)isO(\frac{a}{N})$

for inputs a and $N.$

What is the worst$-$case time complexity of MODSQUAREROOT$($y$,$ N$)$ in Big O

notation and in terms of the inputs N and$/$or y$?$

iii. Briefly explain your solution to part $2$ of $($c$),$ i$.$e$.$ the worst$-$case time complexity

of MODSQUAREROOT$($y$,$ N$).$