The runtime of many recursive algorithms takes the following form:

$T(1)=O(1),T(n)=aT(\frac{n}{b})+O(n^d),$

where $T(n)$ is the runtime of the function on an input of size $n,$ and $a,b,$ and $d$ are constants and that

do not depend on $n.$

$($a$)$ What do $a,b,$ and $d$ represent in terms of the structure of the algorithm?

$($b$)$ We can represent the structure of a recursive algorithm with runtime $T(n)=aT(\frac{n}{b})+O(n^d)$ :

using a tree:

Each dot represents a call

to the recursive function

vdots

vdots

When you get to small enough inputs, hit the base case, and no

further recursive calls. Base cases are the leaves of the tree. Each call to the algorithm is represented by a vertex, the initial call of the function is the root,

and each recursive call produces a child vertex from the vertex of the function that called it$.$ In

terms of $n($the original input size$),a,b,$ and$/$or $d,$ how many levels will this tree have $($from the

root to the leaves$)?$ In other words, how many levels of recursion will there be$?$

$($c$)$ In terms of $n,a,b,$ and$/$or $k,$ how many function calls are there at the $k$ th level of recursion? In

terms of the tree, we can rephrase this question as how many vertices are there in level $k$ below

the root?

$($d$)$ At each level of recursion, the size of the input to the function decreases. If the original call had

an input of size $n,$ in terms of $n,a,b,d,$ and$/$or $k,$ what is the size of the input to the function

calls at level $k?$

$($e$)$ In terms of $n($the original input size$),a,b,d,$ and$/$or $k,$ at a single vertex $($function call$)$ at level

$k,$ how much time $($how many operations$)$ is used by that function call, excluding any operations

done in the recursive calls it makes. For example, in MergeSort, if the input to a function call is

size $m,$ the work done at that call and ignoring the two recursive calls is $O(m),$ because we only

look at non$-$recursive parts of the algorithm, which take time $O(m)$

$($f$)$ In terms of $n($the original input size$),a,b,d,$ and$/$or $k,$ how much time $($how many operations$)$

is used by all function calls at level $k,$ excluding any operations done by the further recursive

calls they make? $($Combine your answers to $($c$)$ and $($e$).)$

$($g$)$ In terms of $n($the original input size$),a,b,$ and$/$or $d$ how much time $($how many operations$)$ is

used by all function calls in the algorithm $($at all levels of recursion$)?($Please leave in summation

notation.$)($h$)$ Use the formula for geometric series:

${\displaystyle \underset{k=0}{\overset{n}{}}}{r}^k=\{\begin{array}{ccc}t+1& if& r=1\\ \frac{r^{2+1}-1}{r-1}& \text{e}\text{l}\text{s}\text{e}& \end{array}$

to evaluate the sum from the previous question.

$($i$)$ If $\frac{a}{b^d}=1,$ what is the big$-$O runtime of the algorithm? You should assume $a,b,$ and $d$ are

constants, and $n$ is the variable that gets large.

$($j$)$ If what is the big$-$O runtime of the algorithm? You should assume $a,b,$ and $d$ are

constants, and $n$ is the variable that gets large.

$($k$)$ If $\frac{a}{b^d}>1,$ what is the big$-$O runtime of the algorithm? You should assume $a,b,$ and $d$ are

constants, and $n$ is the variable that gets large.

$(1)$ You should find that the runtime behaves differently depending on the $3$ possible relationships

between $\frac{a}{b^d}$ and $1.$ Qualitatively explain the behavior in each case. I'll do one case as an example:

if that means that a tends to be small relative to $b$ and $d.$ If $b$ and $d$ are large, that means