To solve the above question, the professor told me to use the property that the

Question

To solve the above question, the professor told me to use the property that the expected height of a randomly built binary search tree on n distinct keys is O(log n). I know the proof of that, however, I don't know how to visualize the binary search algorithm in the given question into subproblems forming a binary search tree. Can you help me how to get there. If you have an alternative solution for this that would help too.

Consider the following silly randomized variant of binary search. You are given a sorted array A of n integers and the integer v that you are searching for is chosen uniformly at random from A. Then instead of comparing v with the value in the middle of the array, the randomized binary search variant chooses a random number r from 1 to n and it compares v with A[r. Depending on whether v is larger or smaller, this process is repeated recursively on the left sub-array or the right sub-array, until the location of v is found. Prove a tight bound on the expected running time of this algorithm

Explanation / Answer

Expected Time complexity of Randomized Binary Search Algorithm

For n elements let say expected time required be T(n), After we choose one random pivot, array size reduces to say k. Since pivot is chosen with equal probability for all possible pivots, hence p = 1/n.

T(n) is sum of time of all possible sizes after choosing pivot multiplied by probability of choosing that pivot plus time take to generate random pivot index.Hence

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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