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 .