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?