SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
Anany Levitin
Chapter:
Fundamentals Of The Analysis Of Algorithm Efficiency
Exercise:
2.1 Exercise
Question:1 | ISBN:9780132316811 | Edition: 3

Question

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

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

Here are the requested details for each of the algorithms:

a)

Computing the sum of n numbers: i. Natural size metric for inputs: n (the number of elements in the list) ii. Basic operation: Addition iii. The basic operation count is typically the same for inputs of the same size since you need to add all n numbers regardless of their values.

b)

Computing n! (n factorial): i. Natural size metric for inputs: n (the input integer) ii. Basic operation: Multiplication iii. The basic operation count can be different for inputs of the same size because the number of multiplications required is directly dependent on the value of n. Larger values of n will require more multiplications.

c)

 Finding the largest element in a list of n numbers: i. Natural size metric for inputs: n (the number of elements in the list) ii. Basic operation: Comparison (to find the largest element) iii. The basic operation count is typically the same for inputs of the same size because you always need to compare all n numbers to find the largest one.

d)

 Euclid’s algorithm (for finding the greatest common divisor): i. Natural size metric for inputs: The size of the input numbers, let's call them a and b. ii. Basic operation: Division (remainder calculation) iii. The basic operation count can be different for inputs of the same size, mainly depending on the values of a and b. In some cases, the algorithm may terminate faster (fewer steps) if the numbers are relatively prime, while in other cases, it may take more steps if the numbers have a common factor.

e)

 Sieve of Eratosthenes (for finding prime numbers up to a given limit): i. Natural size metric for inputs: The limit, denoted as n. ii. Basic operation: Marking or eliminating non-prime numbers from the list. iii. The basic operation count is usually different for inputs of the same size because the density of prime numbers in a given range can vary. In some cases, you may have more primes to find and mark, while in others, fewer.

f)

Pen-and-pencil algorithm for multiplying two n-digit decimal integers: i. Natural size metric for inputs: n (the number of digits in each of the two integers) ii. Basic operation: Multiplication and addition (carrying over) iii. The basic operation count is typically the same for inputs of the same size because you need to perform multiplication and addition for each digit pair, and the number of digits remains constant (n).

0 0

Discussions

Post the discussion to improve the above solution.