Notices
Results 1 to 5 of 5

Thread: algorithm question :

  1. #1 algorithm question : 
    New Member
    Join Date
    Mar 2010
    Posts
    3
    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?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor leohopkins's Avatar
    Join Date
    Dec 2006
    Location
    Dulwich, London, England
    Posts
    1,417
    You have a gross username


    The hand of time rested on the half-hour mark, and all along that old front line of the English there came a whistling and a crying. The men of the first wave climbed up the parapets, in tumult, darkness, and the presence of death, and having done with all pleasant things, advanced across No Man's Land to begin the Battle of the Somme. - Poet John Masefield.

    www.leohopkins.com
    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Mar 2010
    Posts
    3
    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?
    Reply With Quote  
     

  5. #4  
    The Doctor Quantime's Avatar
    Join Date
    Jun 2007
    Location
    United Kingdom
    Posts
    4,546
    "If you wish to make an apple pie from scratch, you must first invent the universe". - Carl Sagan
    Reply With Quote  
     

  6. #5  
    New Member
    Join Date
    Mar 2010
    Posts
    3
    LOL - what do you know! This forum is full of good sports!!!
    Reply With Quote  
     

Bookmarks
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
  •