CODEWITHSUNDEEP
algorithmtime-complexitybinary-search
knowledge_seeker
knowledge_seeker

Reputation: 937

What is the time complexity of the following short algorithm?

I am trying to design and analyse an algorithm similar to the binary search algorithm, but instead of it splitting into halves each time it splits them into either thirds or two thirds.

Here is the pseudocode for it:

BinarySearchThirds(A, low, high, k)
    if low == high
        if A[low] == k
            return low
        else
            return "not found"
    else
        third = third + (high-low)/3
        if key == A[mid]
            return mid
        if key < A[mid]
            return BinarySearchThirds(A, low, third - 1, k)
        else
            return BinarySearchThirds(A, third + 1, high, k)

I am getting that this step return BinarySearchThirds(A, low, third - 1, k) takes T(n/3) and that this step return BinarySearchThirds(A, third + 1, high, k) takes T(2n/3) and so the recurrence equation for this algorithm is T(n) = T(2n/3) + T(n/3) + some_constant_time

I am not sure if this recurrence equation is correct and if so how can it be transformed into a form whereby it can be solved by the master method to get it into a form of theta(...)

Upvotes: 0

Views: 60

Answers (1)

Mo B.
Mo B.

Reputation: 5805

It doesn't matter whether the dividing point is at 1/2 or 2/3 or 999/1000 or whatever fraction. Whenever you have a constant fraction, the number of times you can multiple n with that fraction until you get below 1 is logarithmic in n. It's just the logarithmic base that changes, but the base is irrelevant in the big-o notation, since all logarithms are proportional to each other.

Hence the asymptotic time complexity must be the same as in the standard binary search algorithm, namely O(log n).

Upvotes: 1

Related Questions