ou should find that the runtime behaves differently depending on the $3$ possible relationships

between a

bd and $1.$ Qualitatively explain the behavior in each case. I$$ll do one case as an example:

if a

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

that recursive calls happen on inputs that are much smaller than the original input, and a lot of

time$/$operations are spent $*$not$*$ in recursive calls. If a is small, that means there are not a lot of

recursive calls. Putting these ideas together, we expect that in this case the runtime will $*$not$*$

be strongly dependent on the recursive calls. From our analysis in part $($j$),$ we see that when

a

bd $<1,$ the whole runtime of the algorithm is O$($nd$).$ However, note that the original function

call uses O$($nd time, excluding recursive calls! This means that all of the recursive calls in the

whole algorithm are basically not adding anything significant to the runtime, and the majority

of the runtime is spent at the top of the tree, at the root. This makes sense, given our qualitative

explanation that we expect the runtime to not be strongly affected by recursive calls. $($Now you

should do a similar analysis for the other two cases: a

bd $>1$ and a

bd $=1.)$