Problem:
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.
Question 2- Put the following recurrence relation into closed form:
T(n) = T(n-1)+4n-2
T(1)=3
Question 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?
Please show all the calculations step by step.