Hi, how to solving recurrence relations with divide&conquer? (part1)?

Question

The problem is the following:

Consider the way a drunk would execute MergeSort (we will
call it DrunkMergeSort):

1. Divide the input list of size n into two lists. Because you are drunk, they end
up being of size n/3 and 2n/3 (using ceilings and floors appropriately if n is not
divisible by 3), not n/2 each.

2. Sort the list of size 2n/3 recursively.

3. As you are drunk, you forget to recursively sort the list of size n/3. Everybody
knows the drunks are lucky, so that list just happens to be sorted anyway (thanks,
Bacchus!).

4. Somehow, you manage to apply Merge() on the two sorted lists and produce the
correct result.

---

• What is the asymptotic complexity of the DrunkMergeSort?

• Write the recurrence relation expressing the time complexity of DrunkMergeSort.

Answer 1

Let's look at the recurrence relation first. The division into two lists and the merge are both O(n) operations, so we get
T(n) = T(2n/3) + O(n) <= T(2n/3) + kn for some positive k.
From this it follows that the asymptotic complexity of DrunkMergeSort is in fact O(n). To see this, note that using T(n) = T(2n/3) + kn successively, we get
T(n) = T(2n/3) + kn
= T(4n/9) + k(2n/3) + kn
= T(8n/27) + k(4n/9) + k(2n/3) + kn
and so on; after (-lg n) / (lg 2/3) = r steps we will have
T(1) + kn(1 + 2/3 + 4/9 + ... + (2/3)^r)
This geometric series converges to 3, so T(n) <= T(1) + 3kn = O(n).