CODEWITHSUNDEEP
javatime-complexitybinary-search
Sahar
Sahar

Reputation: 13

Time Complexity of binary search inside a loop


I'm having a hard time to determine what is the time complexity of my solution.
The task was to find the n value of An sequence - 1, 3, 5, 11, 21, 43...

A0 = 1
A1 = 3
An = (An-1)+2*(An-2)

The sequence is "hiding" inside a sorted array.
for example, the following array -
1, 2, 3, 4, 5, 11, 17, 21, 40, 65
will return 4, because A4 = 21, and 21 is the last number of the sequence that appear in the given array.

and for the next array -
-3, -2, 0, 10, 11, 17, 21, 60
the method will return -1, because A0 is not in the array.

my code:

public static int elements(int[] arr)
{
    int i=1, j=3, k, tmp;
    int a=-1;
    tmp =indexOf(arr, i);
    if(tmp==-1)
        return a;
    a++;
    tmp=indexOf(arr,j);
    if(tmp==-1)
        return a;
    a++;
    k=(2*i)+j;
    tmp=indexOf(arr,k);

    while(tmp!=-1)
    {
        tmp=indexOf(arr,k);
        a++;
        i=j;
        j=k;
        k=(2*i)+j;
    }
     return a-1;
}

indexOf() is a O(log n) binary search.

Upvotes: 1

Views: 1585

Answers (1)

Codor
Codor

Reputation: 17595

In the while loop, the search space is never reduced as the same parameter arr is used for indexOf. In the worst case, this means that arr contains a beginning interval of the sequence A and n searches are used, where n is the number of elements in arr. In total, this yields a worst-case runtime complexity of O(n log n).

Upvotes: 1

Related Questions