Jan 12. Recurrences, asymptotics and lower bounds

Recurrence relation for merge sort: Let $T(n)$ denote the time merge sort takes on a list of size $n$. Then we get

$T(n) = 2 T(\frac{n}{2}) + 2n.$

Let us assume for now that $n$ is a power of $2$. Further $T(1)=1$. Then we solve it as follows:

$T(n) = 2 T(\frac{n}{2}) + 2n = 2(2T(\frac{n}{4}) + 2\frac{n}{2}) + 2n = 2n + 2^2 \frac{n}{2} + 2^3 \frac{n}{4} + \dots = 2n (\log n+1).$

Now if $n$ is not a power of $2$, then we can upper bound the running time by $n'$, where $n \le n'$ and $n'$ is a power of $2$. Since there is a power of $2$ between $n$ and $2n$, we obtain an upper bound of $4n (\log{2n}+1) = 4n(\log{n}+2)$ on the running time.

Big Oh: $f(n)$ is said to be $O(g(n))$ if $\exists c > 0, n_0$ such that for every $n > n_0$, $f(n) \le c g(n)$. For example $100n = O(n^2)$.

Big Omega: $f(n)$ is said to be $\Omega(g(n))$ if $\exists c > 0, n_0$ such that $\forall n>n_0$, $f(n) \ge c g(n)$. For example $n\log n = \Omega(100n)$.

Big Theta: $f(n)$ is said to be $\Theta(g(n))$ if $\exists c_1, c_2 > 0$ such that $\forall n>n_0$, $c_1 g(n) \le f(n) \le c_2 g(n)$. For example $n^2 + 10 n = \Theta(n^2)$.

Question: Can there be a comparison-based sorting algorithm that sorts a list with $\Omega(n\log{n})$ comparisons?

Answer: There are $n!$ permutations of $n$ 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 $n!$ possible permutations. Thus the height of the tree is at least $\log{n!}$ and so the running time of a correct sorting algorithm is atleast $\log{n!}$. Note that $\frac{n}{2}^{\frac{n}{2}} \le n!$ and so $log{(n!)} = \Omega(n\log{n})$.

Advertisements