This assignment is about the following algorithm, which multiplies two square ma
ID: 3819529 • Letter: T
Question
This assignment is about the following algorithm, which multiplies two square matrices A and B to produce a new square matrix C. Each matrix has size n × n. The algorithm uses a notation similar to that of the Rosen text.
1 for i := 1 to n
2 for j := 1 to n
3 cij := 0
4 for k := 1 to n
5 cij := cij + aik × bkj
1. (5 points.) Suppose that a primitive operation is either an assignment (:=), an addition (+), or a multiplication (×). How many primitive operations does the algorithm perform? You must count only the primitive operations in lines 3 and 5.
2. (5 points.) Using the result of question 1, prove that the algorithm performs O(n3) primitive operations. You must find constants according to the definition of O on page 205 of Rosen.
3. (10 points.) Using the result of question 1, prove that the algorithm performs more than O(n) primitive operations. You must use the definition of O on page 205 of Rosen.
3.2 The Growth of Functions 205 bubble sort and by the insertion sort to sort a list of n elements. The time required to solve a problem depends on more than only the number of operations it uses. The time also depends on the hardware and software used to run the program that implements the algorithm. However, when we change the hardware and software used to implement an algorithm, we can closely approximate the time required to solve a problem of size n by multiplying the previous time required by a constant. For example, on a supercomputer we might be able to solve a problem of size n a million times faster than we can on a PC. Howeyer, this factor of one million will mot depend on n (except perhaps in some minor ways). One of the advantages of using big-o notation, which we introduce in this section, is that we can estimate the growth of a function without worrying about constant multipliers or smaller order tems. This means that, using big O notation, we do not have to worry about the hardware and software used to implement an algorithm. Furthermore, using big-o notation, we can assume that the different operations used n an algorithm take the same time, which simplifies the analysis considerably. Big-o notation is used extensively to estimate the number of operations an algorithm use as its input grows. With the help of this notation, we can determine whether it is practical to use a particular algorithm to solve a problem as the size of the input increases. Furthermore, using big-o notation, we can compare two algorithms to determine which is more efficient as the size of instance, if we have two algorithms for solving a problem, one the input grows. For using 100m 17n 4 operations and the other using n operations, big-o notation can help us see that the first algorithm uses far fewer operations when n is large, even though it uses more operations for small yalues of n, such as n 10 This section introduces big-o notation and the related big-Omega and big-Theta notations We will explain how big-0. big-Omega, and big-Theta estimates are constructed and establish estimates for some important functions that are used in the analysis of algorithms. Big-O Notation The growth of functions is often described using a special notation. Definition 1 describes this notation DEFINITION 1 Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is Og(x) if there are constants C and k s ch that C g (x) whenever r s is read as (x) is big-oh of g r) Remark: Intuitively, the definition that f (x is x) says that f a) grows slower that some fixed multiple of r as x grows without bound. The constants C and k in the definition of big- O notation are called witnesses to the relationship f (r) is O(g need only one pair of To establish that We witnesses to this relationship. That is, to show tha f (x s e), we need find only one pair of constants C and K, the ch that f (x)ls Clgx) Witnesses, Whenever Note that when there is one pair of witnesses to the relationship f r) is O g (x), there are infinitely many pairs of witnesses. To gee this, note that if C and k are one pair of wi esses then any pair C and k where C C and kExplanation / Answer
1. Inner loop runs n times for each value of I. So, we have n^2 assignment operations. Similarly, line 5 will runs n times for each value of j. So, in total, it will run n^3 times. So, for line 5 we have n^3 assignment operations, n^3 addition operations and n^3 multiplication operations. So, in total we have 3n^3 + n^2 primitive operations.
2.) For c = 10, and n0 = 1, c*n^3 >= (3n^3 + n^2). Hence, it is O(n^3).
3.) Since, we have already proved that given algorithm performs O(n^3) operations. So, (3n^3 + n^2) > c*n. Hence, no. of primitive operations performed by this algorithm is always greater than O(n) operations.