Let n be a nonnegative integer. We are given a list A = a_1, ..., a_n of n posit

ID: 3785456 • Letter: L

Question

Let n be a nonnegative integer. We are given a list A = a_1, ..., a_n 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) if n = 0 then return 0 B:= a_1, a_2, ... a_n-1 if x % a_n = 0 then return 1 + HowManyFactors (B, x) return HowManyFactors (B, x) Prove that this algorithm correctly returns the number of elements in the list A that are factors of x. 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. Use your answer to part (b) find the runtime of this algorithm in theta notation.

Explanation / Answer

The algorithm takes the array of size n and must return the number of factors of x are exist in the list.

Thus the given Algorithm returns the correct value for all inputs.

Each time the algorithm called, the algorithm removes the last element from the array(basic operation) to check whether it is a factor of x or not. It is given that, If n is the size of the array, then O(n) time(linear) or n operations will be required to remove it.

Assume T(n) time required to find factors in a list of n integers,

Then T(n)= T(n-1)+n

Where T(n-1) is the time required to find factors in a list of n-1 integers and n operations required to remove the last(nth) element from the array.

If the array contains only one integer, then the algorithm takes O(1) time to remove it

Thus, T(1)= 1

If the array contains no integers, no removing happens

Thus the initial condition will be as follows:

T(0)=0

Now use substitution method to solve the above recurrence relation

T(n)= T(n-1)+n

= T(n-2)+n-1+n

…

=T(n-i)+n-i+1…+n-1+n

…

=T(n-n)+1+2+…+n-1+n

=T(0) +1+2+…+n-1+n

=n(n+1)/2

=(n2+n)/2

Now,

Since (n2+n)/2 c1*n2 where c1=1, T(n)= =(n2+n)/2 = O(n2)

Since (n2+n)/2 c2*n2 where c2=1/2, T(n)= =(n2+n)/2 = (n2)

Since 0 c2*n2 (n2+n)/2 c1*n2 , T(n)= =(n2+n)/2=(n2)

Navigate

Let n be a nonnegative integer. We are given a list A = a 1 , ..., a n of n posi

Let n be a nonnegative integer. We are given a list A = a_1, ..., a_n of n posit

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let n be a nonnegative integer. We are given a list A = a_1, ..., a_n of n posit

Question

Explanation / Answer

Related Questions

Navigate