Given an array A of n integers, fill an n x n array B such that...

    

Transcribed Image Text:

Given an array A of n integers, fill an n x n array B such that for all i < j, B[i, j] is the alternating sum A[i] - A[i+1]+...+(-1)-A[j]. For i > j, ignore B[i, j]. for i = 1, 2,...,n for j=i+1,...,n compute Ali Ali+1]+...+(-1)-A[j]. store in B[i, j]. (a) What is the running time of the given algorithm as a function of n? Specify a function f such that the running time of the algorithm is (f(n)). (b) Design and analyze a faster algorithm for this problem. You should give an algorithm with running time O(g(n)), where lim, g(n)/f(n) = 0. 8X Given an array A of n integers, fill an n x n array B such that for all i < j, B[i, j] is the alternating sum A[i] - A[i+1]+...+(-1)-A[j]. For i > j, ignore B[i, j]. for i = 1, 2,...,n for j=i+1,...,n compute Ali Ali+1]+...+(-1)-A[j]. store in B[i, j]. (a) What is the running time of the given algorithm as a function of n? Specify a function f such that the running time of the algorithm is (f(n)). (b) Design and analyze a faster algorithm for this problem. You should give an algorithm with running time O(g(n)), where lim, g(n)/f(n) = 0. 8X