**Recurrence relation for merge sort**: Let denote the time merge sort takes on a list of size . Then we get

Let us assume for now that is a power of . Further . Then we solve it as follows:

Now if is not a power of , then we can upper bound the running time by , where and is a power of . Since there is a power of between and , we obtain an upper bound of on the running time.

**Big Oh**: is said to be if such that for every , . For example .

**Big Omega**:** ** is said to be if such that , . For example .

**Big Theta**:** ** is said to be if such that , . For example .

**Question**:** **Can there be a comparison-based sorting algorithm that sorts a list with comparisons?

**Answer**:** **There are permutations of numbers in a list (if they are distinct). Consider a hypothetical algorithm that sorts the list – it makes a comparison and then depending on the outcome it makes some other comparisons. Thus one may view its operation as a binary tree where the leaves are each of the possible permutations. Thus the height of the tree is at least and so the running time of a correct sorting algorithm is atleast . Note that and so .