# algorithms

• March 16th 2010, 08:39 AM
LCopper2010
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!
• March 16th 2010, 02:22 PM
emakarov
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.
• March 16th 2010, 02:25 PM
CaptainBlack
Quote:

Originally Posted by LCopper2010
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