Results 1 to 9 of 9
  1. #1
    itseeker87 is offline Member
    Join Date
    Sep 2008
    Posts
    5
    Rep Power
    0

    Default O(log n) algorithm help !!!!!!

    Hi,

    I have a problem at hand and i kinda need a head start in the same.

    I have an array with some values inside and basically i need to check if the array (index value+1) == the actual value in that index and if so, i need to increase a counter.

    int a[] = {-1, 0, 2, 4, 5, 6, 7}

    and the result shud be 4 for this because ther are 4 elements in this array which satisfy the condition... as, starting from index a[3] till a[6]....the value of index is equal to (index+1)

    like a[3] = 4
    a[4] = 5
    a[5] = 6
    a[6] = 7

    but the catch is to do it in O(log N)...and not o(n).....can someone plz gimme a head start into solving this problem??

    thnx in advance...plz reply soon...its urgent :) thnk yu

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,449
    Rep Power
    25

    Default

    do it in O(log N)...and not o(n).
    Having been away from the textbooks for years, can you explain the difference between those two?

  4. #4
    itseeker87 is offline Member
    Join Date
    Sep 2008
    Posts
    5
    Rep Power
    0

    Default

    Quote Originally Posted by Eranga View Post
    Do you want to increase the value after condition is satisfied?
    There is no need for increase of any value other than a counter which keeps track of the number hits(condition satisfied)...

    So,is there a solution in O(log n) for this problem .... i am guessing that it is a possible for sure as this is part of a project work i am involved in and the specs required an O(log n) solution for this very same problem...

    is it possible??

    thnx...

  5. #5
    itseeker87 is offline Member
    Join Date
    Sep 2008
    Posts
    5
    Rep Power
    0

    Default

    Quote Originally Posted by Norm View Post
    Having been away from the textbooks for years, can you explain the difference between those two?
    O(n) is linear...for example...finding an item in an unsorted list...

    O(log n) logarithmic like Finding an item in a sorted array with a binary search...

    the the sort range half themselves over every iteration, so to speak in the case of O(log n)....

    so given that...is the problem i posted solvable in O(log n) ??

    thnx...

  6. #6
    itseeker87 is offline Member
    Join Date
    Sep 2008
    Posts
    5
    Rep Power
    0

    Default

    Hi,

    sorry for the confusion earlier....

    ONE important point to note is that the array is alwayz assumed SORTED...in ascending order....

    This being the case... is it possible to reach (log n)... i do understand that there is a need to go thru the entire array to arrive at a result(thats the obvious algo which i d think of)....but the specs given for this assignment is that it has to be done in O(log n)....

    let me give a more clearer view to the problem, i hav not been explicit , i am sorry...

    Suppose there is some number N, and there are 7 elements in another array. Each element in the array is given another spl number(one number per element)....say K ...then we hav to form the array by adding the first given value of N (-100) to the spl number K for first array(A) element. The resultant value is the first value of our input array(B). and this value now replaces for the new N. The 2nd element of the input array(B) = first value of array(B) + spl number K for 2nd element of array(A) and so on...

    eg. N = -100 (intial value)
    Array A: {99, 1, 2, 2, 1, 1, 1} [differnt K values]

    then array B becomes

    { -1, 0, 2, 4, 5, 6, 7}.... [explanation -100 + 99 = -1 ---> -1 + 1 = 0---> 0+2= 2---->2+2 =4 ---->4+1=5---->5+1=6--->6+1=7 ]

    it is this array that we have to chk for the condition i posted earlier... (index+1 = value of index)

    At any point of time we can find the array A values for each array B value by subtracting the 2 adjacent index values...i was able to infer this now...does this help with a solution?

    Given this... is it now possible to compute in O(log n) ???

  7. #7
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,449
    Rep Power
    25

    Default

    How does your question relate to Java?
    It looks like you are looking for an algorithm.
    When you get the algorithm, post it and we'll help you write it in java.
    Last edited by Norm; 09-09-2008 at 04:30 PM.

  8. #8
    itseeker87 is offline Member
    Join Date
    Sep 2008
    Posts
    5
    Rep Power
    0

    Default

    yes...but i am implementing the algorithm in java ...

    help please.

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,449
    Rep Power
    25

Similar Threads

  1. Need help - using algorithm statements
    By javanewbie in forum New To Java
    Replies: 2
    Last Post: 07-23-2008, 11:20 AM
  2. Help with algorithm in java
    By coco in forum AWT / Swing
    Replies: 1
    Last Post: 08-01-2007, 06:45 AM
  3. Help with algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 10:26 PM
  4. Help me with this algorithm
    By Marcus in forum Advanced Java
    Replies: 3
    Last Post: 07-02-2007, 01:30 PM
  5. Help with Algorithm
    By Daniel in forum Advanced Java
    Replies: 2
    Last Post: 07-02-2007, 05:51 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •