What is the time complexity of ternary search when applied on doubles?

user_14622758 0
Viewed 85

I know that the time complexity of the normal ternary search is O(log3 n), but what if it is used with floating point numbers?

An Example: What is the time complexity of this block of this block of code?

double s = -100, m1, m2, e = 100, EPS = 1e-6; 
while(abs(s-e) > EPS)
{     
    m1 = s + (e - s) / 3;
    m2 = e - (e - s) / 3;

    if(condition)
        e = m2;
    else
        s = m1;
}

All this does is search for a real number between -100 and 100, but the time complexity changes when the precision of the EPS variable changes.

algorithm
1 Answers

The complexity is O(log 3(e-s)/EPS). We can reduce the problem to the integer case where n=ceil((e-s)/ESP). (Here ceil(x) is the function that maps x to the next integer j such that x <= j < x+1.)

Let delta = (e-s)/n <= EPS. It's easy to verify that delta <= EPS. At the ith step of the algorithm, either s[i] or e[i] has been moved from its predecessor (s[i-1] or e[i-1]) to a different interval I[i] given by I[i] = (s+(i-1)*delta, s+i*delta] (i <= n), or else s[i] and e[i] are within delta of each other, in which case they are within EPS of each other.

user_7807190
Related