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.

Sharing the knowledge gained, is a generous way to change our world for the better. -Sr2Jr

 

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

Question

2. a. Consider the definition-based algorithm for adding two n × 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.

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

a)

Definition-based algorithm for adding two n × n matrices:

  • Basic operation: Addition of two corresponding elements from the input matrices.
  • How many times is it performed as a function of the matrix order n? In this case, each element of the resulting n × n matrix is calculated by adding two elements from the input matrices. Since there are n2 elements in the resulting matrix, the addition operation is performed n2 times as a function of the matrix order n.
  • How many times is it performed as a function of the total number of elements in the input matrices? Each input matrix has n2 elements, so there are a total of 2n2 elements in the input matrices. Therefore, the addition operation is performed 2n2 times as a function of the total number of elements in the input matrices.

b)

 Definition-based algorithm for matrix multiplication:

  • Basic operation: Multiplication and addition of a series of elements from the input matrices.
  • How many times is it performed as a function of the matrix order n? In matrix multiplication, each element of the resulting n × n matrix is calculated by multiplying and adding a series of n elements from the input matrices. Therefore, for each element of the resulting matrix, n multiplications and (n-1) additions are performed. Since there are n2 elements in the resulting matrix, the basic operations (multiplication and addition) are performed n(n-1) times as a function of the matrix order n.
  • How many times is it performed as a function of the total number of elements in the input matrices? Each input matrix has n2 elements, so there are a total of 2n2elements in the input matrices. Therefore, the basic operations (multiplication and addition) are performed 2n2 times as a function of the total number of elements in the input matrices.

In summary, for matrix addition, the basic addition operation is performed n^2 times as a function of the matrix order n and 2n2 times as a function of the total number of elements in the input matrices. For matrix multiplication, the basic multiplication and addition operations are performed n(n-1) times as a function of the matrix order n and 2n2 times as a function of the total number of elements in the input matrices.

0 0

Discussions

Post the discussion to improve the above solution.