Discrete Math: Consider your algorithm from the previous exercise. Here it is: P

Question

Discrete Math: Consider your algorithm from the previous exercise.

Here it is: Please answer : # 1 a b c

1. Construct an algorithm that takes as input a bit string and finds the location of the last 1 in this string or returns 0 if there are no 1s in the string.

a) What is the maximum number of comparisons which must be made in this algorithm?

b) What is the maximum number of times in which you must assign a value to the variable representing the location of the last 1 in this algorithm?

c) Determine the sum of your answers from parts (a) and (b).Find a big O-estimate for this value

procedure example ( a1 , a2, a3 , .... n= however many a's )

i:= 1 to n ?

for ?

else 0

return

Explanation / Answer

The algorithm to find the last 1 in a string is as follows:

a) int pos_last_1(string str)

{

len= str.length();

for(i=len-1;i>=0;i--)

{

if(str[i]=='1')

return (i+1);

}

return 0;

}

In the above algorithm, the maximum number of comparisons needed is n where n is the length of the string. Thus time complexity for the comparisons is O(n).

We are directly returning the position when 1 is found from the end. Thus time complexity of the algorithm is O(n)+O(1) = O(n).

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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