Master Theorem

So for the past week, we've been doing Master Theorem. It was quite confusing at the beginning, since it is hard to believe that complicated recursive functions runtime can be analysed so easily with it. So here's the "formula" for Master Theorem:


T(n) = (n^d)             if a < b^d
          (n^d log n)     if a = b^d
          (n^(logb a))    if a > b^d

I found some exercises online and figured out that it actually works. It is a short-cut or like a cheat sheet without going through the long process of unwinding to get to the answer. This is definitely one of the most interesting theorems that I've ever encounter with.

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.

First Post

I might be kind of late for my first post since I saw a lot of people started blogging already, but I'll make sure I will post regularly till the end of this semester. 

Tomorrows the first midterm and to prepare for it, I went through the notes and redo example in lectures. I think I'm pretty good at doing mathematical and complete induction proofs since assignment 1 was very helpful for me to understand the structure and thinking process to proving. Well-ordering proofs and structural induction are still kind of new to me but I'm sure I will get the grasp of it before the test tomorrow. 

Well, I think I should get back to studying. Good luck to all my fellow CSC236 classmates~~