Answer Happy

Section 2.1 1. For each of the following algorithms, indicate (i) a natural size metric for its inputs, (ii) its basic operation, and (iii) whether the basic operation count can be different for inputs of the same size: a. computing the sum of n numbers b. computing n! c. finding the largest element in a list of n numbers d. Euclid's algorithm e. sieve of Eratosthenes f. pen-and-pencil algorithm for multiplying two n-digit decimal integers 2. a. Consider the definition-based algorithm for adding two n x n matrices. What is its basic operation? How many times is it performed as a function of the matrix order n? As a function of the total number of elements in the input matrices? b. Answer the same questions for the definition-based algorithm for matrix multiplication.