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!

Printable View

- Mar 16th 2010, 08:39 AMLCopper2010algorithms
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! - Mar 16th 2010, 02:22 PMemakarov
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.

- Mar 16th 2010, 02:25 PMCaptainBlack
This is exactly the same as sorting into ascending order a list of length $\displaystyle 4$.

So how would you do this?

Now if $\displaystyle N$ is the length of our arbitrary list and $\displaystyle 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 $\displaystyle O(1)$, that is the time is independent of the length of the full list.

CB