Answer the following questions: (a) Fill in the blanks to complete the following
ID: 3694411 • Letter: A
Question
Answer the following questions:
(a) Fill in the blanks to complete the following recursive function:
//Comptes the sum of the items between fromIndex and toIndex
int Sum (int info[], int fromIndex, int toIndex)
{
if (fromIndex xxx toIndex)
return xx ;
else
return xx ;
}
(b) Which is the base case and which is the general calse?
(c) Show how you would call this function to summ all the elements in an array called numbers, which contains elements indexed from 0 to MAX IT EMS 1.
(d) Use the Three-Question Method to verify the function.
(e) What run-time problem migth you experience with this function as it is now coded?
Explanation / Answer
int sum(int info[],int fromindex,int toindex)
{
if(fromindex<toindex)
return info[fromindex]+sum(info,fromindex++,toindex); /*in every call we are incrementing from index and add element at from index .
else
return info[fromindex];
}
b)Base case:
if(fromindex>=toindex)
return info[fromindex] that is the case written in else part is base case.
c)suppose if we have an array A[]={1,2,3,4,5} and here fromindex=0, and toindex=4
function call is as follows:
sum(A,fromindex,toindex);
d)Three question method to verify the function:
Base case: base case returns the last element to add to the sum.
Smaller caller: The function is involves the smaller case of the original problem in every call the size of the array decrements by 1.
General Case:
The general case executes recursively to add all the elements in the given array until fromindex is less than toindex.
e)(e) What run-time problem migth you experience with this function as it is now coded?
It is a linear problem whose time complexity is proportional to the size of the array ,which is taking O(n) time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.