Let n be a nonnegative integer We are given a list A a1 an

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. How Many Factor s(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 % an = 0 then return 1 + How Many Factor s (B, x) return How Many Factor s(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 Theta notation.

Solution

Solution:

Part a)-

There are three methods for proving that any algorithm is true or false

i)-using mathematical induction

ii)- using loop invariant

iii)-taking some example

prove of correctness Using mathematical induction.

In mathematics induction two steps are sufficient for this purpose:

1. Prove that an algorithm is true for the base case.

2. Assume that algorithms is true for some k. then Derive from here that algorithms is also true for k+1 the inductive step

Here the base case is if the factor n=0 then its return 0 means if we divide any number by 0 we got this the base case where our algorithm is terminated

Means number/x= true so we are not considering 0 as a factor.

And the factor is starting from 1 because number/1 = number or number% factor==0 this Condition is true

Note-----Here B contains the list of all number starting from 1 to n-1,

This is true for base case when 1 is an factor.

The algorithm is recursive when this find any factor it will count the number the factor and call the same algorithm.

If this is true for base case then we can prove it for some value k where 1<k<n-1

If number%k==0 then k is factor of number (using modular operator) and we count the k is a factor of number it.

Same it is true for k+1, if(number%k+1==0)

So we can say it is true for n-1.

prove of correctness Using Loop invariant:

There are three conditions for Loop invariant

i)-our algorithms will be true for when loop is initialized.

ii)- our algorithms will be true for when loop is executed

iii)- our algorithms will be true for when loop is terminated

At the start of each iteration of recursive call we have one factor of number.

Initialization: Before the first iteration the invariant holds zero since the factor value is zero.

Maintenance: The loop invariant is maintained at each iteration, since otherwise at the i-th recursive call there is some factor whose satisfied the condition that x%n_i =0 such that. However, in that case for the k-th iteration of the we have at least k number of factor and those factors are independent to previous factor and belongs to B.

Termination: When the loop terminates or recursion (after k^th iteration where k=n-1) we counted all the number of factor those are belongs to b.

Part b)-

Recurrence Relation is :

T (n) = T (n-1) +1 where n>=1, T (1) =1

Part c)-

Solution of Recurrence Relation:

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

Using Substitution Method.

T (n) = T (n-1) + 1              // Now we put n=n-1to 1and we get equation below

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

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

.                  .         .

.                  .         .

T(2)= T(1)+1

__________________________add all the recurrence

T(n)= T(1)+1+1+1+1…..+1 put T(1)=1

T(n)= 1+1+1+1+1…..+1

T(n)=1+1+1+………….1= k times where 1<k<n

T (n)= O(n)

Here worst case and average case is same because we find all the factor of number until not traverse all the number from 1 to n-1.

O (n) = (n)