Question

Q1. Count the total number of multiplications and divisions in the following code in terms on n. Assume that the values of all variables are given for k-1:n-1 for i-K+1:n end end X(n)-B(n)/A(n,n); for i-n-1:-1:1 for j-i+1:n s-s-A(ij)*XG); end

Answer 1

Count the number of times each for loop runs for k = 1: n - 1 this loop runs (n - 1) times for i = k + 1: n this loop runs (n - k) times but k varies from 1 to n - 1 Hence total number of Multiplications in B(i) = B(i) - A(i, k) * B(k) with these two loos is sigma^n - 1_k = 1 (n - k) sigma^n - 1_k = 1 (n - k) = n (n - 1) - n (n - 1)/2 = n (n - 1)/2 for i = n - 1: 1 this loop runs for (n - 1) times for j = i + 1: n this loop runs for (n - i) times but i varies from n - 1 to 1 \r\n Hence total number of multiplication s = s - A(i, j) * x(j) with these two loop is sigma^1_i = n - 1 (n - i) sigma^1_i = n - 1 = n (n - 1) - n(n - 1)/2 = n (n - 1)/2 overall multiplications = n (n - 1)/2 + n (n - 1)/2 = n (n - 1)