Design and Analysis of Algorithms

432 Design and Analysis of Algorithms

Give O bounds on the complexity of your op-

erations as a function of argument size.

15.4 Using your implementation in the previous

problem, code the Russian peasants’ method

of raising a bignum to a power. Analyse the

complexity of raising a fi xed constant to a

power. See how well your analysis agrees

with empirical observations.

15.5 Explore the possibility of speeding up big-

num multiplication using the divide-and-con-

quer strategy.

15.6 Empirically compare the performance of a

spell checker using hashing against ones us-

ing (a) binary search (b) a trie. Assume that

you need not consider the time taken ...