1.) Integer multiplication can be defines as mult(m,n) = m for n=1 m + mult(m,n-
ID: 3564205 • Letter: 1
Question
1.) Integer multiplication can be defines as
mult(m,n) = m for n=1
m + mult(m,n-1) for n>1
Write a recursive function that multiplies integers using this equation. Then give the recurrence relation for the number of additions and subtractions that are done by your function.
2.) put the following recurrence relation into closed form:
T(n) = T(n-1)+4n-2
T(1)=3
3.) What is the average complexity of sequential search if there is a .75 chance that the target will not be found in the list and there is a .25 chance that when the target is in the list, it will be found in the first half of the list?
Explanation / Answer
Q1:
ANSWER
#include <iostream>
using namespace std;
int mul(int n,int m)
{
if(m<=1)
{
return n;
}
return n+mul(n,m-1);
}
int main()
{
int num,num1;
cout<<"Enter the 1st number number : ";
cin>>num;
cout<<"Enter the second number : ";
cin>>num1;
cout<<mul(num,num1);
}
Q2:
Answer Solution if you need then i'll give you but know i'm telling you closed relation is O(n^2)
Q3 :
ANSWER O(N)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.