Thread: algorithm question :

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?

You have a gross username

Well, I must say, I got the inspiration from Family Guy, where Brian films Stew watching it on Youtube. That was a good laugh. Now, what about my post? Is my way right?

LOL - what do you know! This forum is full of good sports!!!