Results 1 to 2 of 2

Math Help - Algorithm to find the median number

  1. #1
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1

    Algorithm to find the median number

    This is an algorithm to find the median number of a sequence of numbers, it works in linear time in average case: Quickselect. (It can even find the n:th smallest element)

    But I think this algorithm works in linear time in all cases: BFPRT. But that depends on the Median of Medians algorithm. If the Median of Medians algorithm does find a number that is guaranteed to be greater than or equal to at least X % of the numbers and smaller than or equal to at least X % of the numbers, where X is a constant, then the BFPRT algorithm does work in linear time in worst case, I believe. But what is X and how can you show that? (Then it even works in liear time in worst case when it is going to find the n:th smallest element)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Quote Originally Posted by TriKri View Post
    This is an algorithm to find the median number of a sequence of numbers, it works in linear time in average case: Quickselect. (It can even find the n:th smallest element)

    But I think this algorithm works in linear time in all cases: BFPRT. But that depends on the Median of Medians algorithm. If the Median of Medians algorithm does find a number that is guaranteed to be greater than or equal to at least X % of the numbers and smaller than or equal to at least X % of the numbers, where X is a constant, then the BFPRT algorithm does work in linear time in worst case, I believe. But what is X and how can you show that? (Then it even works in liear time in worst case when it is going to find the n:th smallest element)
    Maybe I should add where X is a constant > 0. By the way, here is some wikipedia links if someone wants to read about the algorithms:
    Quickselect, based onm the Quicksort algorithm
    BFPRT, uses the Median of Medians algorithm (I believe)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Thomas algorithm number operations
    Posted in the Advanced Math Topics Forum
    Replies: 6
    Last Post: November 25th 2011, 05:08 AM
  2. How To Find The Median And Variance?
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 21st 2010, 05:18 PM
  3. Number distribution algorithm
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 19th 2008, 04:56 PM
  4. increasing / decreasing number algorithm (recursive)
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: July 24th 2008, 10:09 AM
  5. How to find the mean, median and mode
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 25th 2008, 09:09 AM

Search Tags


/mathhelpforum @mathhelpforum