Questions

coequal.

a$.T(n)=4T(\frac{n}{4})+n$

b$.T(n)=2T(\frac{n}{2})+nlogn$

c$.T(n)=6T(\frac{n}{3})+n^2$

d$.T(n)=10T(\frac{n}{2})+n^{2}lo{g}^{1\mathrm{.}5}(n)$

e$.T(n)=4T(\frac{n}{4})+1000n$

In the introductory lecture on Divide and Conquer, an example algorithm for using divide and conquer for multiplication of integers was given, along with an optimization under the assumption that the second parameter, $b,$ was even.

a$.(5$ pts$)$ Considering the optimized version, for what input values will the algorithm work? Will it work for any even $b,$ or is the restriction more significant than that. Why is this the case?

b$.(5$ pts$)$ Adjust the optimized algorithm so that it will work for arbitrary integer values of $b.$ Prove, or at least argue, the correctness of your approach. The algorithm should retain $(logb)$ worst case performance.

the same size, $n.$

and $n($i$.$e$.,$ do not treat $k$ as a constant in the analysis, but rather use a cost function of the form $T(k,n)=$dots $).$

in Big$-$Theta notation in terms of $k$ and $n.$ Is it any better than the algorithm from part a$?$

you think it is more efficient?

addition, we can think of exponentiation as repeated multiplication. Consider the calculation of $a^n,$

a$.(5$ pts$)$ Provide a divide and conquer algorithm for calculating $a^n$ assuming a logarithmic time multiplication operation is used. State the recurrence relation. Can it be solved using The Master Theorem as is$?$

b$.(5$ pts$)$ Solve the recurrence relation, making simplifying assumptions if necessary. Ensure that you explicitly state any assumptions that you make.

made to get there$).$

optimization provide any benefit for either of them? Why or why not?