For each of the following algorithms, indicate (i) a natural size metric for its inputs, (ii) its basic operation, and (
Posted: Mon Jun 06, 2022 5:27 pm
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
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