Time Complexity of binary search inside a loop

Question

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.

I'm not sure that the growth rate of An even matters here, as in the worst case all values in the array correspond to a term in the series, and thus indexOf will be called n + 1 times (returning -1 after the last time when it reaches the end). Thus the complexity is just O(n log n). If your question was in fact about the growth rate of An, Wolfram Alpha says it is ϴ(2^n). — meowgoesthedog
– meowgoesthedog, Commented Jan 31, 2018 at 10:16

Codor · Accepted Answer · 2018-01-31 10:17:16Z

1

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).

answered Jan 31, 2018 at 10:17

Codor

17.6k9 gold badges32 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

meowgoesthedog Over a year ago

Perhaps one should explain to OP that the growth rate of An does not matter at all, and (if this is a homework/exam question) it was probably included as a trick

Collectives™ on Stack Overflow

Time Complexity of binary search inside a loop

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related