Results 1 to 8 of 8

Math Help - Algorithm

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    Algorithm

    Let A be a 1- dimensional array with integers and "min" , "max", "number"
    three integer numbers. find an algorithm that answers, if the value "number" is in the array e.g a [i] = number for some i, 1<= min <= i <= max <= n, and the complexity of the algorithms must be O(lgn)

    I need some help on that! Thanks in advance!
    Last edited by liberty; November 19th 2009 at 07:41 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by liberty View Post
    Let A be a 1- dimensional array with integers and "min" , "max", "number"
    three integer numbers. find an algorithm that answers, if the value "number" is in the array e.g a [i] = number for some i, 1<= min <= i <= max <= n, and the complexity of the algorithms must be O(lgn)

    I need some help on that! Thanks in advance!
    The existence of max and min should not effect the problem, so you may as well answer the problem of finding an algorithm to determine if "number" is in the array of length n with (time) complexity O(\ln(n)) (or are we after the average complexity over all possible max and min?)

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by CaptainBlack View Post
    ....
    (or are we after the average complexity over all possible max and min?)
    CB
    hmmmmm......
    The solution,(the algorithm) sould be implemented via a function (in a programming concept) and min max number should be arguments of the function. The function returns 1 if number is in the array and 0 otherwise. If the array was sorted, its binary searching that works. But the array is not sorted.
    about the last question: hmm it talks about time complexity and not average time complexity...But its a good question anyway..I had not thought about that at all !
    Thanks for your reply..it helps me.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by liberty View Post
    hmmmmm......
    The solution,(the algorithm) sould be implemented via a function (in a programming concept) and min max number should be arguments of the function. The function returns 1 if number is in the array and 0 otherwise. If the array was sorted, its binary searching that works. But the array is not sorted.
    about the last question: hmm it talks about time complexity and not average time complexity...But its a good question anyway..I had not thought about that at all !
    Thanks for your reply..it helps me.
    Your explanation made it foggier.

    "min max number should be arguments of the function. The function returns 1 if number is in the array and 0 otherwise."

    array[10][30][20][40][60][70]
    Function MMN( min=13, max=37, num=60)

    Should the function check for values outside the given minimum and maximum arguments?
    I do not understand the reason for min/max being arguments to the function if you only want to know whether the number is in the array.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by aidan View Post
    Your explanation made it foggier.

    "min max number should be arguments of the function. The function returns 1 if number is in the array and 0 otherwise."

    array[10][30][20][40][60][70]
    Function MMN( min=13, max=37, num=60)

    Should the function check for values outside the given minimum and maximum arguments?
    I do not understand the reason for min/max being arguments to the function if you only want to know whether the number is in the array.
    Because the function may search in a sub array of the array.
    Min max define the sub array.
    In your example array[10][30][20][40][60][70]
    10 is the first and 70 is the last. And there are 6 elements. If min = 1 and max = 6 and number is 20 function returns 1. Is there. But if min = 5 and max = 6 and number = 20 then function returns 0.Is not in that sub-array. But the worst (most difficult) case is for min = 1 and max = 6. Because the sub array in this case is the array. And the time complexity is dominated by this case.
    Last edited by liberty; November 21st 2009 at 12:41 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by liberty View Post
    Because the function may search in a sub array of the array.
    Min max define the sub array.
    Which is why they are irrelevant for a worst case complexity since this must occur when min=1 and max=n

    CB
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by CaptainBlack View Post
    Which is why they are irrelevant for a worst case complexity since this must occur when min=1 and max=n

    CB
    I agree..I have bad news..
    The reason that i post this, was that my believe was that the question is wrong. You cant make an algorithm that it works in O(lgn) if the array is not sorted. (Beacause you must check all the elements, if the array is not sorted) And today i learned that this is true. I had asked if the question was wrong and if should be given that array is sorted, and they ansewred you must deal with the general case. But today i asked again and...
    ok...
    aidan, CaptainBlack,sorry and
    MANY THANKS!!
    Thank you guys.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by liberty View Post
    I agree..I have bad news..
    The reason that i post this, was that my believe was that the question is wrong. You cant make an algorithm that it works in O(lgn) if the array is not sorted. (Beacause you must check all the elements, if the array is not sorted) And today i learned that this is true. I had asked if the question was wrong and if should be given that array is sorted, and they ansewred you must deal with the general case. But today i asked again and...
    ok...
    aidan, CaptainBlack,sorry and
    MANY THANKS!!
    Thank you guys.
    If the list is sorted then binary search should do this in O(ln(n))

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 02:46 AM
  2. Algorithm help
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 12th 2009, 04:10 AM
  3. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: July 16th 2008, 01:29 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 01:02 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2007, 11:47 PM

Search Tags


/mathhelpforum @mathhelpforum