What is the time complexity for this algorithm? I looked over it myself and got

Question

What is the time complexity for this algorithm? I looked over it myself and got that it was n^2 but I'm not really sure. My logic is that the while loop executes n times and at least one of the if-else loops will also run n times making it n^2.

Algorithm TernarySearch (x int, a(1)....a(n) int, output: loc int)
i=1;
j=1n;
remaining=j-1+1;
while (remaining > 1)
interval = floor(remaining/3);
m1=i + interval;
m2= i+2*interval
if (x <= a(m1))
j=m1;
else if (x <= a(m2))
i=m1+1;
j=m2;
else
i=m2+1;
endelsif
remaining = j-1+1;
endwhile

if (remaining == 1 and x not equal a(i)) return loc = 0;
else return loc = j;

Explanation / Answer

PS: Please rate the answer Ternary search is not n^2. Its log(3/2)n (read as log n to the base 3/2) The while loop does not execute n times. You are splitting the range into 3 parts in ternary search. And you see to which part does the element of interest belong to. Then you split that part further into 3 more parts and so on. So the number of times you split the range is log(3/2)n to reach the last element. This is the maximum time your while loop executes. Your if statements are just comparisons and they execute in a constant number of instructions irrespective of n. So they are not included in complexity/running time computations. Hope you understood. If its too confusing, you can first refer why binary search is log(2)n and then you will know why this is log(3/2)n

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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