Results 1 to 3 of 3

Math Help - algorithms

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    15

    algorithms

    Write the algorithm that puts the first four terms of a list of arbitrary length in increasing order. Show that this algorithm has time complexity O(1) in terms of number of comparisons used.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Well, if you are given four apples and you have glasses that allow you seeing at most two apples at a time, are you able to arrange them in increasing order? If yes, then write your sequence of actions in a programming language you are using. Also, try to figure out the maximum number of comparisons you need to make to do the job.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by LCopper2010 View Post
    Write the algorithm that puts the first four terms of a list of arbitrary length in increasing order. Show that this algorithm has time complexity O(1) in terms of number of comparisons used.

    Thanks!
    This is exactly the same as sorting into ascending order a list of length 4.

    So how would you do this?

    Now if N is the length of our arbitrary list and t_4 is the time to put the first four terms in order this time is obviously independent of the length of the full list. Which is exactly what it means for it to have time complexity O(1), that is the time is independent of the length of the full list.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithms
    Posted in the Math Software Forum
    Replies: 2
    Last Post: November 4th 2010, 09:25 PM
  2. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 8th 2010, 10:48 PM
  3. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 17th 2009, 08:11 AM
  4. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2009, 04:06 AM
  5. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 12:33 PM

Search Tags


/mathhelpforum @mathhelpforum