Hey there. I am taking this course (intro to algorithm and data structures) and I got a question from my homework, which I am not sure about. It'll be very nice if you can help and tell me if I've answered it correctly and fully.

Anyway,** the question** goes like this :

the following pseudo-code is a binary-search :

Code:

BINARY-SEARCH(A,p,r,v)
if p>r
then return NIL
q<-ceil( (p+r)/2 )
if v<A[q]
then return BINARY-SEARCH(A,p,q-1,v)
else if v>A[q]
then return BINARY-SEARCH(A,q+1,r,v)
else return q
RECURSIVE-BINARY-SEARCH(A,v)
BINARY-SEARCH(A,1,length(A),v)

Rewrite this pseudo-code in a way that it will separate the array to 2 parts. the first one is length(A)/3 long and the second one is 2*length(A)/3 long. In addition, prove that in this case, the complexity is Theta(log_2 n)

**My answer** : this is the new pseudo-code :

Code:

BINARY-SEARCH(A,p,r,v)
if p>r
then return NIL
q<-ceil( (p+r)/3 )
if v<A[q]
then return BINARY-SEARCH(A,p,q-1,v)
else if v>A[q]
then return BINARY-SEARCH(A,q+1,r,v)
else return q
RECURSIVE-BINARY-SEARCH(A,v)
BINARY-SEARCH(A,1,length(A),v)

and this is my IDEA of proof :

From that we can conclude that the recurrence relation is :

Code:

T(n) = { T(n/3)+O(1) if v<A[q]
{ T(2n/3)+O(1) if v>A[q]

In the worst case, in every iteration v>A[q], and

in the best case, in every iteration v<A[q]. Therefore

T(n)=T(n/3)+O(1)

is the recurrence relation in the best case, and

T(n)=T(2n/3)+O(1)

is the recurrence relation in the worst case.

If we'll prove that T(n/3)+O(1)=Theta(lgn) and T(2n/3)+O(1)=Theta(lgn)

then we can conclude that T(n)=Theta(lgn). In order to prove that T(2n/3)+O(1)=Theta(lgn) and T(n/3)+O(1)=Theta(lgn) I'll use master method.

Is this right?