Problem

1. Write algorithms that perform the operations where u represents a large integer, m is a nonnegative integer, divide returns the quotient in integer division, and rem returns the remainder. Analyze your algorithms, and show that these operations can be done in linear time.

2. Modify Algorithm 2.9 (Large Integer Multiplication) so that it divides each n-digit integer into

(a) Three smaller integers of n/3 digits (you may assume that n = 3^k).

(b) Four smaller integers of n/4 digits (you may assume that n = 4^k).

Analyze your algorithms, and show their time complexities in order notation.

Attachment:- Algorithm 2.9.rar