# Time complexity of sorting

([home](https://github.com/alexhkurz/introduction-to-programming/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/SkIGSnPTU) ... [next](https://hackmd.io/@alexhkurz/Sy7AHDNn8))

Let us think about a simple algorithm for sorting a list of words or numbers.

## A sorting algorithm

We start with a list $[a_1,a_2,\ldots a_n]$.

The algorithm goes through the list element by element and builds a new sorted list.

After the first step the new list is $[a_1]$.

(Every list containing only one element is sorted.)

Then we take the next element $a_1$, compare whether $a_2<a_1$ ...

... and make a new sorted list, which is either $[a_2,a_1]$ or $[a_1,a_2]$.

And so on it goes.

## Time complexity

To measure the time complexity, we do not want to measure actual run time because the run time does not depend only on the algorithm but also on its implementation and the hardware.

We are looking for a measure of time that depends only on the problem.

A typical measure for evaluating the efficiency of different sorting algorithms is the number of comparisons such as when we compared $a_2<a_1$ above.

**Activity:** Continue the table below

| # elements to be sorted | # comparisons |
|:---:|:---|
|1|0|
|2|1|
|3|3|
|4|6|

If you think that the number of comparison depends on the order of the list we start with you are right. Fill the table so that you account for the worst case.

**Activity:** Which of the following would you say best describes the time complexity of the algorithm?

- linear
- quadratic
- exponential

**Activity:** Let us denote by $x$ the number of elements to be sorted and by y the number of comparisons. Can you find numbers $a,b,c$ such that

$$y=ax^2 +bx +c\quad?$$

**Activity:** Can you find a proof showing that the formula above is correct for all number $x$ of elements to be sorted? [Hint: The sequence above is known as triangle numbers. To count the number of elements in the triangle, turn it into a rectanble first.]