3. (10 points) Consider the following pseudocode that finds x in a list of sorte

Question

3. (10 points) Consider the following pseudocode that finds x in a list of sorted numbers by using ternary search. The algorithm is simlar to binary search, only it splits the current list into three parts (instead of two) and checks which part x may be in. Thus at each step, the algorithm removes 2/3 of the items in the current list Find the complexity of the algorithm. Is it faster or slower asymptotically than binary search? Algorithm TernarySearch (x int, a(1). . .a (n) int, output: loc int) i-li J=n; remaining = 1+1; while (remaining > 1) interval = floor (remaining/3) ; m1 = 1+interval; m2 = i+2*interval; if (x

Explanation / Answer

t(n) = t(n/3) + c

from master theorem,

a=1, b=3 and k=0 and p=0

a = b^k and p>-1

t(n) = O(log n)

So aymptotically, both the algo have same complexity.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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