This exercise develops an algorithm to compute ?? for a given positive integer n. Consider the following algorithm:

k = ?(len(n) ? 1)/2?,

for i = k ? 1 down to 0

do if ?n then

output m

(a) Show that this algorithm correctly computes ? n?. // not necessary but if you can solve it please do provide me. Thanks.

(b) In a straightforward implementation of this algorithm, each loop iteration takes time O(len(n)^2), yielding a total running time of O(len(n)^3). Give a more careful implementation, so that each loop iteration takes time O(len(n)), yielding a total running time is O(len(n)^2). // I did not understand this question. I thought big- oh was O(k) for this.

No spam please:

Vn Vn