Let n be a nonnegative integer. We are given a list A = a 1 , ..., a n of n posi
ID: 3010905 • Letter: L
Question
Let n be a nonnegative integer. We are given a list A = a1, ..., an of n positive integers and a positive integer x. We will compute the number of list elements that are factors of x. Here is a recursive algorithm to solve this problem, where % is the modulus operator.
HowManyFactors(A: list of n positive integers, x: positive integer)
1. if n = 0 then
2. return 0
3. B := a1, a2, ..., an-1
4. if x % an = 0 then
5. return 1 + HowManyFactors(B,x)
6. return HowManyFactors(B,x)
a) Prove that this algorithm correctly returns the number of elements in the list A that are factors of x.
b) Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Assume that the list A is stored in a data structure such that removing an element from the list takes time linear in the number of list elements.
c) Use your answer to part (b) find the runtime of this algorithm in ? notation.
Picture of the question:
3. Let n be a nonnegative integer. We are given a list A = a,..·An of n positive integers and a positive integer z. We will compute the number of list elements that are factors of x. Here is a recursive algorithm to solve this problem, where % is the modulus operator. HowManyFactors(A list of n positive integers, r : positive integer) I. if n 0 then 2. return 0 3. B :=a1,a2 , ,an-1 5. return 1 + HouManyFactors(B, z) 6. return HowManyFactors(B,z) (a) (4 points) Prove that this algorithm correctly returns the number of elements in the list A that are factors of r (b) (2 points) Let T(n) be the running time of this algorithm. Write a recurrence relation that T(n) satisfies. Assume that the list A is stored in a data structure such that removing an element from the list takes time linear in the number of list elements. 2 (c) (2 points) Use your answer to part (b) find the runtune of this algorithm in notation.Explanation / Answer
a) The number A is of the form a1,a2,...,an, we are checking the conditions that x divides an then we are returning 1 + HowmanyFactors(B,x), otherwise we are returning HowmanyFactors(B,x)
This code snippet will run for n times
So after the n iterations, we will have the count of the numbers (a1,a2,...,an) which is divisible by the input number x
b) T(n) = T(n-1) + O(n)
T(n-1) = T(n-2) + O(n)
T(n) = T(1) + O(n) + O(n-1) + O(n-2) + ....
Hence the order of T(n) will be equal to n^2
c) The runtime of the algorithm will be Theta(n^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.