1. 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?  2.

3. You have a gross username    4. 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?  5.   6. LOL - what do you know! This forum is full of good sports!!!  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement