Problem 3. Consider the following recurrence, defined for n a power of 4 (for the time of some algorithm): T(n) = 3 if n = 1 2T(
n/4) + 4n + 1 otherwise (a) Calculate T(16) by hand. Show your work. (b) Use the tree method to solve the recurrence exactly, assuming n is a power of 4. (c) Use the formula to calculate T(1). Show your work. (d) Use the formula to calculate T(4). Show your work. (e) Use the formula to calculate T(16). Show your work. (f) Use Mathematical Induction to prove that your formula is correct in general.
1 answer:
You might be interested in
Answer:
The Matlab code is as given in the explanation, paste the code in the new script file, save it and run.
Explanation:
The code is as follows
Code:
<em>%% Initialization of the code</em>
<em>% The code takes an array of six AIS scores of the form [AIS1 AIS2 AIS3</em>
<em>% AIS4 AIS5 AIS6] of order 1x6.</em>
<em>AIS=input('Please enter the AIS array of the form [AIS1 AIS2 AIS3 AIS4 AIS5 AIS6]');%taking input of the array</em>
<em>AISs=sort(AIS,'descend');%sorting the array in the descending order</em>
<em>iss=(AISs(1,1)^2)+(AISs(1,2)^2)+(AISs(1,3)^2);%Calculating the ISS</em>
<em>disp(['The injury severity score (ISS) for the entered array is ', num2str(iss)])%Displaying the output</em>
Output:
<u><em>Please enter the AIS array of the form [AIS1 AIS2 AIS3 AIS4 AIS5 AIS6][3 0 4 5 3 0];</em></u>
<u><em>The injury severity score (ISS) for the entered array is 50</em></u>
<u><em /></u>
