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}).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s