CODEWITHSUNDEEP
javasearchif-statementbig-otime-complexity
Donald
Donald

Reputation: 1340

Big O Complexity of method

I am having problems analyzing this method for its Big O complexity. In fact, I am also unsure of how the method works due to its confusing nature. For now, all I figure out is that the a "gradually shrinking range" in the array will be searched for a given number. Could someone please explain the following code and guide me as to how I can analyze its complexity?

static int foo(int a[], int u, int l, int x) {
    while(l <= u) {
        int s = (u-l+1)/3, f = l+s, b = f+s;
        if(a[f] == x)
            return f;
        else if(a[b] == x)
            return b;
        else if(a[f] > x)
            u = f-1;
        else if(a[b] > x)
            l = b+1;
        else {
            l = b-1;
            u = f+1;
        }
    }
    return -1;
}

Upvotes: 1

Views: 136

Answers (3)

Terry Li
Terry Li

Reputation: 17268

It is a ternary search, whose complexity is still O(lgn).

Upvotes: 0

Floris
Floris

Reputation: 46395

It looks like this code is searching a sorted array a for a value x between a lower index k and upper index u. It does this by adjusting both ends of the interval in which it is searching, with a series of clauses that adjust either the lower or upper bound included in the search. The step size of the search s is one third of the range (u - l_ + 1), and the "tentative new bounds" are f and b. Depending on whether the solution is in the new range or now, the algorithm narrows down the search to a new region that is one third of the old.

To get a good feeling for how it works I suggest you print out the numbers l and u for each iteration of the loop; then increase the size of x (for example, double it each time) and repeat.

When you plot the number of loops vs x, you will quickly see whether, for large x, you get a straight line, a parabola, or something else. You can gain some insights from this; and with a bit of luck the relationship will quickly become clear.

Recognize that most of the time you will adjust down to 1/3 of the size, so the number of iterations goes up only slowly with size of interval - in fact, 3x bigger interval takes just one more iteration. That is the hallmark of a O(log(n)) process.

Upvotes: 0

iluxa
iluxa

Reputation: 6969

Seems l=low, u=upper, so u-l is the range. S is then one third of the range. The method does strange things, but in each iteration the range shrinks by one third.

If the range shrank by half (like binary search), that would clearly be log n. But this way, shrinking by a third each time.. What do you think?

Upvotes: 1

Related Questions