The following algorithm, Find01, takes as input a binary string of length n grea

Question

The following algorithm, Find01, takes as input a binary string of length n greaterthanorequalto 2 whose bits are b_1, b_2, ellipsis, b_n that starts with 0 and ends with 1. This algorithm returns a position i such that b_i = 0 and b_i+1 = 1. Find01 (b_1, b_2, ellipsis, b_n: binary string of length n greaterthanorequalto 2 with b_1 = 0 and b_n = 1) 1. if n = 2 then 2. return 1 3. mid: = [n/2] 4. if b_mid = 0 and b_mid+1 = 1 then 5. return mid 6. else if b_mid = 1 and b_mid+1 = 1 then 7. return Find01 (b_1, ellipsis, b_mid) 8. else 9. return mid + Find01(b_mid+1, ellipsis, b_n) (a) Prove that Find01 is correct. (b) Give an example of a best-case input of size n = 6. Explain why this is a best-case input. (c) What is the order of the algorithm in Theta notation, in the best case? Show how you get to your answer, using any valid method (d) Give an example of a worst-case input of size n = 6. Explain why this is a worst-case input (e) What is the order of the algorithm in Theta notation, in the worst case? Show how you get to your answer, using any valid method.

Explanation / Answer

(a) We know that b starts with 0 and ends with 1. Now we calculate mid and we divide b in to left and right halves. Now we have 4 cases.

We have 4 cases:

b(mid) = 0 and b(mid+1)=1 --> We got the answer

b(mid) = 1 and b(mid+1)=1 --> Now we know that b starts with 0, so we know for sure there is atleast one 0 on left side of b and b(mid)=1 so (b(1)..b(mid)) starts with a 0 and ends with a 1. So there must a change from 0 to 1 at somepoint. So now we only consider the left part of b.

b(mid) = 1 and b(mid+1)=0 & b(mid) = 0 and b(mid+1)=0 --> In these both cases we know that b ends with 1, so we know for sure there is atleast one 1 on right side of b and b(mid+1)=0 so (b(mid+1)..b(n)) starts with a 0 and ends with a 1. So there must a change from 0 to 1 at somepoint. So now we only consider the right part of b.

Hence in all the four cases we arrive at an answer.

(b) 000111 -> In this case b(mid)=0 and b(mid+1)=1, so we get the answer in the first iteration itself.

(c) The best case time taken is (1)

(d) 011111 -> In this case the shift from 0 to 1 happens at the beginning itself, so we have to break b two times in order to arrive at the answer. This is the maximum number of times b can be broken in pieces.

(e) The worst case time taken is (logn).

T(n) = T(n/2) + O(1)

Using masters method. a=1,b=2,c=0
log(b)a = 0 and c=0
So T(n) = (logn)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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