Unwinding...

So today's lecture we went through the complexity of merge sort. Before proving it, most of us already know that the worst case is O(n lg n), but I was amazed by the unwinding process of breaking the code into pieces and analysing it to reach the point that shows us it's n lg n. Here is the following code:


MergeSort(A,b,e):
    if b == e: return
    m = (b + e) / 2
    MergeSort(A,b,m)
    MergeSort(A,m+1,e)
    # merge sorted A[b..m] and A[m+1..e] back into A[b..e]
    for i = b,...,e: B[c] = A[c]
    c = b
    d = m+1
    for i = b,...,e:
        if d > e or (c <= m and B[c] < B[d]):
            A[i] = B[c]
            c = c + 1
        else: # d <= e and (c > m or B[c] >= B[d])
            A[i] = B[d]
            d = d + 1

In lecture, we treated all the lines that don't depend on n as constant 1 (which make things simpler), and lines with loop as n. In the code, you can see that it calls itself (recursion) on line 4 and 5 with length of half of the original list. So we can let them have time complexity of T(⌈n/2⌉) and T(⌊n/2⌋). At the end, the function for the time complexity is:

    T(n) = {1 if n=1
                 T(⌈n/2⌉) +  T(⌊n/2⌋) + n + 1 if n>1}

By unwinding, we use T(2^k). So,
    T(2^k) = 2T(⌈2^k/2⌉) + 2^k + 1
                = 2T(2^(k-1)) + 2^k + 1
                = 2(T(2^(k-1)) + 2^k + 1) + 2^k + 1
                = 2^2 T(2^(k-2)) + 2(2^k) + 3
                = 2^2 (2 T(2^(k-3)) + 2^(k-2) + 1) + 2(2^k) + 3
                = 2^3 T(2^(k-3)) + 3(2^k) + 7
                ...
                = 2^i  T(2^(k-i) + i 2^k + 2^i - 1
                ...
                = 2^k T(2^(k-k) + k 2^k + 2^k - 1
                = n + n lg n + n - 1        (Since 2^k = n)
                = n lg n + 2n - 1

So we are convinced that Merge Sort has Θ(n lg n).
I personally think that this is a very useful way to analyse recursive codes, so I will explore more kind of recursive sorting code to really understand the unwinding method.
I'll blog again next week.
- Brian out.