In the present module, it was demonstrated that you could estimate the exponent of the asymptotic time complexity (i. e., a of O(na)) by plotting the runtime of an algorithim as a function of the problem size on a log-log plot and determining the slope of the resulting line. In this problem, you will write a function that uses this methodology to estimate a given the runtimes and associated problem sizes. Write a function called estTC with the following declaration line
begin code
function alpha estTC(nSize, runTime)
end code
where the input arguments are:
• nSize: a 1-by-n array whose elements are the problem size for each test
• runtime: a k-by-n array where each row is the runtimes for an algorithm tested at each problem size. Thus the number of rows corresponds to the number of algorithms.
The output argument, alpha, is a k-by-1 array that contains the estimate of the exponent for each of the k algorithms.
The estTC function should first transform both of the input arguments using the base-10 logarithm (i. e., log10 in MATLAB). Then, using regression you should fit an linear function (i. e., of the form f(x) = ax + 3) to the transformed input data. As seen in the module, the slope of this function will then be an estimate for a, the exponent of the asymptotic time complexity.
You should test this function using the data from the previous problem. Additionally in the assignment download there is a runTimeData. mat file that contains runtime data for 4 operations involving matrices. The first row corresponds to vector-vector multiplication (i. e., xTy where x and y are n-by-1 vectors). The first row corresponds to matrix-vector multiplication (i. e., Ay where y is a n-by-1 vector and A is a n-by-n matrix). The third row corresponds to matrix- matrix multiplication (i. e., AB where A and B are n-by-n matrices). The fourth row corresponds to solving a system of linear equations Ax = b (i. e., where b is a n-by-1 vector and A is a n-by-n matrix). An example using this function with the supplied data is given below.
begin code load runTimeData 2 3 alpha = estTC(nSize, runTime) 4 5 alpha 6 7 8 0.8193 1.8465 2.8224 2.5852 9 10 end code