$[15$ points$]$

Consider the following Java code snippet, which for non$-$negative inputs returns an integer

between low and high that, when squared, is equal to $x,$ and which returns $-1$ if no such

integer exists:

public static int sqrt$($int x$,$ int low, int high$)\{$

if $($low $>$ high $||$ x $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ low $<mtext></mtext><mn>0</mn><mtext></mtext><mi>|</mi><mi>|</mi>$ high $<mtext></mtext><mn>0</mn><mi>)</mi>$

return $-1$;

int p $=$ low $+($high $-$ low$)/2$;

if $($p $*$ p $==$ x$)$

return p;

else if $($ p $*$ p $>$ x$)$

return sqrt$($x$,$ low, p $-1)$;

else

return sqrt$($x$,$ p $+1,$ high$)$;

$\}$

a$.[3$ points$]$

In an arbitrary recursive call to sqrt$,$ let d$1$ equal high $-$ low, and let d$2$ equal what high

$1$ ow will be for the next recursive call, assuming that both d $1$ and d $2$ are positive. What must

$\underset{d1}{lim}\frac{d1}{d2}$ be under these conditions?

Hint: Your answer should simplify to an integer. Think of this ratio as the number of

approximately equal$-$sized partitions into which you're breaking the set of integers between low

and high $($inclusive$)$ for this arbitrary recursive call, where in the next recursive call you're only

considering values in one of these partitions.

b$.[4$ points$]$

Under the same assumptions listed in part $($a$),$ for the initial call to sqrt$,$ we can express the

difference high $-1$ow $($the number of integers on which we are initially considering for the

search$)$ as approximately equal to $a^r,$ where $a$ is the number of approximately equal$-$sized

partitions into which we break our consideration set $($the value you calculated in part $($a$))$ and $r$ is

the maximum number of recursive calls to sqrt we can go through $($depending on $x)$ before the

desired integer is found or is determined to not exist. Solve the equation high $-$low$=a^r$ for

the approximate value of $r,$ based on the value you calculated for $a,$ in terms of the arbitrary

initial inputs high and low.

c$.[3$ points$]$

What is the tightest big O $($or equivalently, just big $)$ worst$-$case running time complexity of

sqrt$,$ in terms of the input variables x $,$ high, and low $($assuming they are all positive$)?$

Simplify your answer.

d$.[5$ points$]$

What is the tightest big O $($or equivalently, just big $)$ space complexity of extra memory

required when running sqrt $($original implementation$),$ in terms of the input variables x $,$ high,

and low $($assuming they are all positive$)?$ Simplify your answer.

Hint: Consider memory used on the call stack and space required by any new variables.