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

Question

more questions following from problem of part1

• Derive the asymptotic time complexity of DrunkMergeSort. Note that the recurrence
relation does not match exactly the requirements of the Master Theorem. You
can use unfolding or an argument about the work done on each recursive level to
derive the solution.

• Can you strengthen the statement of the Master Theorem a bit? How?

• Maybe you are not THAT drunk and remember to apply the (AlmostDrunkMerge-
Sort) recursively also on the sequence of the length n/3. How would the recurrence
relation look like now?

• Can you derive the asymptotic time complexity of AlmostDrunkMergeSort?

Answer 1

The asymptotic time complexity I answered in part 1.

Looking at the Master Theorem, this nearly falls under case 3:
T(n) = aT(n/b) + f(n)
where a = 1, b = 3/2, and f(n) is an unknown function of order n. Now log_b (a) = 0, so f(n) = Ω(n^(0+ε)) for any 0 < ε <= 1. So for case 3 we just need that 1.f(2n/3) <= c.f(n) for some c < 1 and for sufficiently large n.

Since we know f(n) is Θ(n), we know there are constants s and t (s > t) such that
f(n) >= tn for sufficiently large n
f(2n/3) <= s(2n/3) for sufficiently large n
and hence f(2n/3) <= s(2/3)n = (s/t)(2/3) tn <= (s/t) (2/3) f(n).
So this works if s/t < 3/2, but we can't guarantee this.

If we replace f(n) by an upper bound kn, as we did for part 1, this does fall under case 3, since then 1.(2kn/3) <= c.kn for all 2/3 <= c < 1.

I don't really see an obvious strengthening of the Master Theorem from this.

AlmostDrunkMergeSort: the recurrence relation is
T(n) = T(n/3) + T(2n/3) + O(n).
We repeat our previous procedure of using an upper bound of kn:
T(n) = T(n/3) + T(2n/3) + kn
= T(n/9) + T(2n/9) + k(n/3) + T(2n/9) + T(4n/9) + k(2n/3)
= T(n/9) + 2T(2n/9) + T(4n/9) + kn
= T(n/27) + T(2n/27) + kn/9 + 2T(2n/27) + 2T(4n/27) + 4kn/9 + T(4n/27) + T(8n/27) + 4kn/9 + kn
= T(n/27) + 3T(2n/27) + 3T(4n/27) + T(8n/27) + 2kn
= ...
= Σ (i=0 to j) C(j, i) T((2^i/3^j)n) + j(kn)
after j steps, where C(j, i) means j choose i; the last line written out corresponds to j = 3.
The longets path will be for j = log_(2/3) n, when all the T terms will be constant at most and we will get the asymptotic time complexity as log_(2/3) n (kn) = Θ(n log n).